1.    1  <?php
2.    2 
3.    3 /**
4.    4  * Pure-PHP arbitrary precision integer arithmetic library.
5.    5  *
6.    6  * Supports base-2, base-10, base-16, and base-256 numbers.  Uses the GMP or BCMath extensions, if available,
7.    7  * and an internal implementation, otherwise.
8.    8  *
9.    9  * PHP versions 4 and 5
10.   10  *
11.   11  * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
12.   12  * {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
13.   13  *
14.   14  * Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
15.   15  * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction.  Because the largest possible
16.   16  * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
17.   17  * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
18.   18  * used.  As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
19.   19  * which only supports integers.  Although this fact will slow this library down, the fact that such a high
20.   20  * base is being used should more than compensate.
21.   21  *
22.   22  * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format.  ie.
23.   23  * (new Math_BigInteger(pow(2, 26)))->value = array(0, 1)
24.   24  *
25.   25  * Useful resources are as follows:
26.   26  *
27.   27  *  - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
28.   28  *  - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
29.   29  *  - Java's BigInteger classes.  See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
30.   30  *
31.   31  * Here's an example of how to use this library:
32.   32  * <code>
33.   33  * <?php
34.   34  *    include 'Math/BigInteger.php';
35.   35  *
36.   36  *    $a = new Math_BigInteger(2);
37.   37  *    $b = new Math_BigInteger(3);
38.   38  *
39.   39  *    $c = $a->add($b);
40.   40  *
41.   41  *    echo $c->toString(); // outputs 5
42.   42  * ?>
43.   43  * </code>
44.   44  *
45.   45  * LICENSE: Permission is hereby granted, free of charge, to any person obtaining a copy
46.   46  * of this software and associated documentation files (the "Software"), to deal
47.   47  * in the Software without restriction, including without limitation the rights
48.   48  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
49.   49  * copies of the Software, and to permit persons to whom the Software is
50.   50  * furnished to do so, subject to the following conditions:
51.   51  *
52.   52  * The above copyright notice and this permission notice shall be included in
53.   53  * all copies or substantial portions of the Software.
54.   54  *
55.   55  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
56.   56  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
57.   57  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
58.   58  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
59.   59  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
60.   60  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
61.   61  * THE SOFTWARE.
62.   62  *
63.   63  * @category  Math
64.   64  * @package   Math_BigInteger
65.   65  * @author    Jim Wigginton <terrafrost@php.net>
66.   66  * @copyright 2006 Jim Wigginton
67.   67  * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
68.   68  * @link      http://pear.php.net/package/Math_BigInteger
69.   69  */
70.   70 
71.   71 /**#@+
72.   72  * Reduction constants
73.   73  *
74.   74  * @access private
75.   75  * @see self::_reduce()
76.   76  */
77.   77 /**
78.   78  * @see self::_montgomery()
79.   79  * @see self::_prepMontgomery()
80.   80  */
81.   81 define('MATH_BIGINTEGER_MONTGOMERY', 0);
82.   82 /**
83.   83  * @see self::_barrett()
84.   84  */
85.   85 define('MATH_BIGINTEGER_BARRETT', 1);
86.   86 /**
87.   87  * @see self::_mod2()
88.   88  */
89.   89 define('MATH_BIGINTEGER_POWEROF2', 2);
90.   90 /**
91.   91  * @see self::_remainder()
92.   92  */
93.   93 define('MATH_BIGINTEGER_CLASSIC', 3);
94.   94 /**
95.   95  * @see self::__clone()
96.   96  */
97.   97 define('MATH_BIGINTEGER_NONE', 4);
98.   98 /**#@-*/
99.   99 
100.  100 /**#@+
101.  101  * Array constants
102.  102  *
103.  103  * Rather than create a thousands and thousands of new Math_BigInteger objects in repeated function calls to add() and
104.  104  * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
105.  105  *
106.  106  * @access private
107.  107  */
108.  108 /**
109.  109  * $result[MATH_BIGINTEGER_VALUE] contains the value.
110.  110  */
111.  111 define('MATH_BIGINTEGER_VALUE', 0);
112.  112 /**
113.  113  * $result[MATH_BIGINTEGER_SIGN] contains the sign.
114.  114  */
115.  115 define('MATH_BIGINTEGER_SIGN', 1);
116.  116 /**#@-*/
117.  117 
118.  118 /**#@+
119.  119  * @access private
120.  120  * @see self::_montgomery()
121.  121  * @see self::_barrett()
122.  122  */
123.  123 /**
124.  124  * Cache constants
125.  125  *
126.  126  * $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
127.  127  */
128.  128 define('MATH_BIGINTEGER_VARIABLE', 0);
129.  129 /**
130.  130  * $cache[MATH_BIGINTEGER_DATA] contains the cached data.
131.  131  */
132.  132 define('MATH_BIGINTEGER_DATA', 1);
133.  133 /**#@-*/
134.  134 
135.  135 /**#@+
136.  136  * Mode constants.
137.  137  *
138.  138  * @access private
139.  139  * @see self::Math_BigInteger()
140.  140  */
141.  141 /**
142.  142  * To use the pure-PHP implementation
143.  143  */
144.  144 define('MATH_BIGINTEGER_MODE_INTERNAL', 1);
145.  145 /**
146.  146  * To use the BCMath library
147.  147  *
148.  148  * (if enabled; otherwise, the internal implementation will be used)
149.  149  */
150.  150 define('MATH_BIGINTEGER_MODE_BCMATH', 2);
151.  151 /**
152.  152  * To use the GMP library
153.  153  *
154.  154  * (if present; otherwise, either the BCMath or the internal implementation will be used)
155.  155  */
156.  156 define('MATH_BIGINTEGER_MODE_GMP', 3);
157.  157 /**#@-*/
158.  158 
159.  159 /**
160.  160  * Karatsuba Cutoff
161.  161  *
162.  162  * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
163.  163  *
164.  164  * @access private
165.  165  */
166.  166 define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 25);
167.  167 
168.  168 /**
169.  169  * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
170.  170  * numbers.
171.  171  *
172.  172  * @package Math_BigInteger
173.  173  * @author  Jim Wigginton <terrafrost@php.net>
174.  174  * @access  public
175.  175  */
176.  176 class Math_BigInteger
177.  177 {
178.  178     /**
179.  179      * Holds the BigInteger's value.
180.  180      *
181.  181      * @var array
182.  182      * @access private
183.  183      */
184.  184     var $value;
185.  185 
186.  186     /**
187.  187      * Holds the BigInteger's magnitude.
188.  188      *
189.  189      * @var bool
190.  190      * @access private
191.  191      */
192.  192     var $is_negative = false;
193.  193 
194.  194     /**
195.  195      * Precision
196.  196      *
197.  197      * @see self::setPrecision()
198.  198      * @access private
199.  199      */
200.  200     var $precision = -1;
201.  201 
202.  202     /**
203.  203      * Precision Bitmask
204.  204      *
205.  205      * @see self::setPrecision()
206.  206      * @access private
207.  207      */
208.  208     var $bitmask = false;
209.  209 
210.  210     /**
211.  211      * Mode independent value used for serialization.
212.  212      *
213.  213      * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
214.  214      * a variable that'll be serializable regardless of whether or not extensions are being used.  Unlike $this->value,
215.  215      * however, $this->hex is only calculated when $this->__sleep() is called.
216.  216      *
217.  217      * @see self::__sleep()
218.  218      * @see self::__wakeup()
219.  219      * @var string
220.  220      * @access private
221.  221      */
222.  222     var $hex;
223.  223 
224.  224     /**
225.  225      * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
226.  226      *
227.  227      * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
228.  228      * two's compliment.  The sole exception to this is -10, which is treated the same as 10 is.
229.  229      *
230.  230      * Here's an example:
231.  231      * <code>
232.  232      * <?php
233.  233      *    include 'Math/BigInteger.php';
234.  234      *
235.  235      *    $a = new Math_BigInteger('0x32', 16); // 50 in base-16
236.  236      *
237.  237      *    echo $a->toString(); // outputs 50
238.  238      * ?>
239.  239      * </code>
240.  240      *
241.  241      * @param $x base-10 number or base-$base number if $base set.
242.  242      * @param int $base
243.  243      * @return Math_BigInteger
244.  244      * @access public
245.  245      */
246.  246     function __construct($x = 0, $base = 10)
247.  247     {
248.  248         if (!defined('MATH_BIGINTEGER_MODE')) {
249.  249             switch (true) {
250.  250                 case extension_loaded('gmp'):
251.  251                     define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP);
252.  252                     break;
253.  253                 case extension_loaded('bcmath'):
254.  254                     define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH);
255.  255                     break;
256.  256                 default:
257.  257                     define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL);
258.  258             }
259.  259         }
260.  260 
261.  261         if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
262.  262             // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
263.  263             ob_start();
264.  264             @phpinfo();
265.  265             $content = ob_get_contents();
266.  266             ob_end_clean();
267.  267 
268.  268             preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
269.  269 
270.  270             $versions = array();
271.  271             if (!empty($matches[1])) {
272.  272                 for ($i = 0; $i < count($matches[1]); $i++) {
273.  273                     $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
274.  274 
275.  275                     // Remove letter part in OpenSSL version
276.  276                     if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
277.  277                         $versions[$matches[1][$i]] = $fullVersion;
278.  278                     } else {
279.  279                         $versions[$matches[1][$i]] = $m[0];
280.  280                     }
281.  281                 }
282.  282             }
283.  283 
284.  284             // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
285.  285             switch (true) {
286.  286                 case !isset($versions['Header']):
287.  287                 case !isset($versions['Library']):
288.  288                 case $versions['Header'] == $versions['Library']:
289.  289                 case version_compare($versions['Header'], '1.0.0') >= 0 && version_compare($versions['Library'], '1.0.0') >= 0:
290.  290                     define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
291.  291                     break;
292.  292                 default:
293.  293                     define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
294.  294             }
295.  295         }
296.  296 
297.  297         if (!defined('PHP_INT_SIZE')) {
298.  298             define('PHP_INT_SIZE', 4);
299.  299         }
300.  300 
301.  301         if (!defined('MATH_BIGINTEGER_BASE') && MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL) {
302.  302             switch (PHP_INT_SIZE) {
303.  303                 case 8: // use 64-bit integers if int size is 8 bytes
304.  304                     define('MATH_BIGINTEGER_BASE',       31);
305.  305                     define('MATH_BIGINTEGER_BASE_FULL',  0x80000000);
306.  306                     define('MATH_BIGINTEGER_MAX_DIGIT',  0x7FFFFFFF);
307.  307                     define('MATH_BIGINTEGER_MSB',        0x40000000);
308.  308                     // 10**9 is the closest we can get to 2**31 without passing it
309.  309                     define('MATH_BIGINTEGER_MAX10',      1000000000);
310.  310                     define('MATH_BIGINTEGER_MAX10_LEN',  9);
311.  311                     // the largest digit that may be used in addition / subtraction
312.  312                     define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 62));
313.  313                     break;
314.  314                 //case 4: // use 64-bit floats if int size is 4 bytes
315.  315                 default:
316.  316                     define('MATH_BIGINTEGER_BASE',       26);
317.  317                     define('MATH_BIGINTEGER_BASE_FULL',  0x4000000);
318.  318                     define('MATH_BIGINTEGER_MAX_DIGIT',  0x3FFFFFF);
319.  319                     define('MATH_BIGINTEGER_MSB',        0x2000000);
320.  320                     // 10**7 is the closest to 2**26 without passing it
321.  321                     define('MATH_BIGINTEGER_MAX10',      10000000);
322.  322                     define('MATH_BIGINTEGER_MAX10_LEN',  7);
323.  323                     // the largest digit that may be used in addition / subtraction
324.  324                     // we do pow(2, 52) instead of using 4503599627370496 directly because some
325.  325                     // PHP installations will truncate 4503599627370496.
326.  326                     define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 52));
327.  327             }
328.  328         }
329.  329 
330.  330         switch (MATH_BIGINTEGER_MODE) {
331.  331             case MATH_BIGINTEGER_MODE_GMP:
332.  332                 switch (true) {
333.  333                     case is_resource($x) && get_resource_type($x) == 'GMP integer':
334.  334                     // PHP 5.6 switched GMP from using resources to objects
335.  335                     case is_object($x) && get_class($x) == 'GMP':
336.  336                         $this->value = $x;
337.  337                         return;
338.  338                 }
339.  339                 $this->value = gmp_init(0);
340.  340                 break;
341.  341             case MATH_BIGINTEGER_MODE_BCMATH:
342.  342                 $this->value = '0';
343.  343                 break;
344.  344             default:
345.  345                 $this->value = array();
346.  346         }
347.  347 
348.  348         // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
349.  349         // '0' is the only value like this per http://php.net/empty
350.  350         if (empty($x) && (abs($base) != 256 || $x !== '0')) {
351.  351             return;
352.  352         }
353.  353 
354.  354         switch ($base) {
355.  355             case -256:
356.  356                 if (ord($x[0]) & 0x80) {
357.  357                     $x = ~$x;
358.  358                     $this->is_negative = true;
359.  359                 }
360.  360             case 256:
361.  361                 switch (MATH_BIGINTEGER_MODE) {
362.  362                     case MATH_BIGINTEGER_MODE_GMP:
363.  363                         $this->value = function_exists('gmp_import') ?
364.  364                             gmp_import($x) :
365.  365                             gmp_init('0x' . bin2hex($x));
366.  366                         if ($this->is_negative) {
367.  367                             $this->value = gmp_neg($this->value);
368.  368                         }
369.  369                         break;
370.  370                     case MATH_BIGINTEGER_MODE_BCMATH:
371.  371                         // round $len to the nearest 4 (thanks, DavidMJ!)
372.  372                         $len = (strlen($x) + 3) & 0xFFFFFFFC;
373.  373 
374.  374                         $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
375.  375 
376.  376                         for ($i = 0; $i < $len; $i+= 4) {
377.  377                             $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
378.  378                             $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
379.  379                         }
380.  380 
381.  381                         if ($this->is_negative) {
382.  382                             $this->value = '-' . $this->value;
383.  383                         }
384.  384 
385.  385                         break;
386.  386                     // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
387.  387                     default:
388.  388                         while (strlen($x)) {
389.  389                             $this->value[] = $this->_bytes2int($this->_base256_rshift($x, MATH_BIGINTEGER_BASE));
390.  390                         }
391.  391                 }
392.  392 
393.  393                 if ($this->is_negative) {
394.  394                     if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
395.  395                         $this->is_negative = false;
396.  396                     }
397.  397                     $temp = $this->add(new Math_BigInteger('-1'));
398.  398                     $this->value = $temp->value;
399.  399                 }
400.  400                 break;
401.  401             case 16:
402.  402             case -16:
403.  403                 if ($base > 0 && $x[0] == '-') {
404.  404                     $this->is_negative = true;
405.  405                     $x = substr($x, 1);
406.  406                 }
407.  407 
408.  408                 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
409.  409 
410.  410                 $is_negative = false;
411.  411                 if ($base < 0 && hexdec($x[0]) >= 8) {
412.  412                     $this->is_negative = $is_negative = true;
413.  413                     $x = bin2hex(~pack('H*', $x));
414.  414                 }
415.  415 
416.  416                 switch (MATH_BIGINTEGER_MODE) {
417.  417                     case MATH_BIGINTEGER_MODE_GMP:
418.  418                         $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
419.  419                         $this->value = gmp_init($temp);
420.  420                         $this->is_negative = false;
421.  421                         break;
422.  422                     case MATH_BIGINTEGER_MODE_BCMATH:
423.  423                         $x = (strlen($x) & 1) ? '0' . $x : $x;
424.  424                         $temp = new Math_BigInteger(pack('H*', $x), 256);
425.  425                         $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
426.  426                         $this->is_negative = false;
427.  427                         break;
428.  428                     default:
429.  429                         $x = (strlen($x) & 1) ? '0' . $x : $x;
430.  430                         $temp = new Math_BigInteger(pack('H*', $x), 256);
431.  431                         $this->value = $temp->value;
432.  432                 }
433.  433 
434.  434                 if ($is_negative) {
435.  435                     $temp = $this->add(new Math_BigInteger('-1'));
436.  436                     $this->value = $temp->value;
437.  437                 }
438.  438                 break;
439.  439             case 10:
440.  440             case -10:
441.  441                 // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
442.  442                 // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
443.  443                 // [^-0-9].*: find any non-numeric characters and then any characters that follow that
444.  444                 $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
445.  445 
446.  446                 switch (MATH_BIGINTEGER_MODE) {
447.  447                     case MATH_BIGINTEGER_MODE_GMP:
448.  448                         $this->value = gmp_init($x);
449.  449                         break;
450.  450                     case MATH_BIGINTEGER_MODE_BCMATH:
451.  451                         // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
452.  452                         // results then doing it on '-1' does (modInverse does $x[0])
453.  453                         $this->value = $x === '-' ? '0' : (string) $x;
454.  454                         break;
455.  455                     default:
456.  456                         $temp = new Math_BigInteger();
457.  457 
458.  458                         $multiplier = new Math_BigInteger();
459.  459                         $multiplier->value = array(MATH_BIGINTEGER_MAX10);
460.  460 
461.  461                         if ($x[0] == '-') {
462.  462                             $this->is_negative = true;
463.  463                             $x = substr($x, 1);
464.  464                         }
465.  465 
466.  466                         $x = str_pad($x, strlen($x) + ((MATH_BIGINTEGER_MAX10_LEN - 1) * strlen($x)) % MATH_BIGINTEGER_MAX10_LEN, 0, STR_PAD_LEFT);
467.  467                         while (strlen($x)) {
468.  468                             $temp = $temp->multiply($multiplier);
469.  469                             $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr($x, 0, MATH_BIGINTEGER_MAX10_LEN)), 256));
470.  470                             $x = substr($x, MATH_BIGINTEGER_MAX10_LEN);
471.  471                         }
472.  472 
473.  473                         $this->value = $temp->value;
474.  474                 }
475.  475                 break;
476.  476             case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
477.  477             case -2:
478.  478                 if ($base > 0 && $x[0] == '-') {
479.  479                     $this->is_negative = true;
480.  480                     $x = substr($x, 1);
481.  481                 }
482.  482 
483.  483                 $x = preg_replace('#^([01]*).*#', '$1', $x);
484.  484                 $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
485.  485 
486.  486                 $str = '0x';
487.  487                 while (strlen($x)) {
488.  488                     $part = substr($x, 0, 4);
489.  489                     $str.= dechex(bindec($part));
490.  490                     $x = substr($x, 4);
491.  491                 }
492.  492 
493.  493                 if ($this->is_negative) {
494.  494                     $str = '-' . $str;
495.  495                 }
496.  496 
497.  497                 $temp = new Math_BigInteger($str, 8 * $base); // ie. either -16 or +16
498.  498                 $this->value = $temp->value;
499.  499                 $this->is_negative = $temp->is_negative;
500.  500 
501.  501                 break;
502.  502             default:
503.  503                 // base not supported, so we'll let $this == 0
504.  504         }
505.  505     }
506.  506 
507.  507     /**
508.  508      * PHP4 compatible Default Constructor.
509.  509      *
510.  510      * @see self::__construct()
511.  511      * @param $x base-10 number or base-$base number if $base set.
512.  512      * @param int $base
513.  513      * @access public
514.  514      */
515.  515     function Math_BigInteger($x = 0, $base = 10)
516.  516     {
517.  517         $this->__construct($x, $base);
518.  518     }
519.  519 
520.  520     /**
521.  521      * Converts a BigInteger to a byte string (eg. base-256).
522.  522      *
523.  523      * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
524.  524      * saved as two's compliment.
525.  525      *
526.  526      * Here's an example:
527.  527      * <code>
528.  528      * <?php
529.  529      *    include 'Math/BigInteger.php';
530.  530      *
531.  531      *    $a = new Math_BigInteger('65');
532.  532      *
533.  533      *    echo $a->toBytes(); // outputs chr(65)
534.  534      * ?>
535.  535      * </code>
536.  536      *
537.  537      * @param bool $twos_compliment
538.  538      * @return string
539.  539      * @access public
540.  540      * @internal Converts a base-2**26 number to base-2**8
541.  541      */
542.  542     function toBytes($twos_compliment = false)
543.  543     {
544.  544         if ($twos_compliment) {
545.  545             $comparison = $this->compare(new Math_BigInteger());
546.  546             if ($comparison == 0) {
547.  547                 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
548.  548             }
549.  549 
550.  550             $temp = $comparison < 0 ? $this->add(new Math_BigInteger(1)) : $this->copy();
551.  551             $bytes = $temp->toBytes();
552.  552 
553.  553             if (empty($bytes)) { // eg. if the number we're trying to convert is -1
554.  554                 $bytes = chr(0);
555.  555             }
556.  556 
557.  557             if (ord($bytes[0]) & 0x80) {
558.  558                 $bytes = chr(0) . $bytes;
559.  559             }
560.  560 
561.  561             return $comparison < 0 ? ~$bytes : $bytes;
562.  562         }
563.  563 
564.  564         switch (MATH_BIGINTEGER_MODE) {
565.  565             case MATH_BIGINTEGER_MODE_GMP:
566.  566                 if (gmp_cmp($this->value, gmp_init(0)) == 0) {
567.  567                     return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
568.  568                 }
569.  569 
570.  570                 if (function_exists('gmp_export')) {
571.  571                     $temp = gmp_export($this->value);
572.  572                 } else {
573.  573                     $temp = gmp_strval(gmp_abs($this->value), 16);
574.  574                     $temp = (strlen($temp) & 1) ? '0' . $temp : $temp;
575.  575                     $temp = pack('H*', $temp);
576.  576                 }
577.  577 
578.  578                 return $this->precision > 0 ?
579.  579                     substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
580.  580                     ltrim($temp, chr(0));
581.  581             case MATH_BIGINTEGER_MODE_BCMATH:
582.  582                 if ($this->value === '0') {
583.  583                     return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
584.  584                 }
585.  585 
586.  586                 $value = '';
587.  587                 $current = $this->value;
588.  588 
589.  589                 if ($current[0] == '-') {
590.  590                     $current = substr($current, 1);
591.  591                 }
592.  592 
593.  593                 while (bccomp($current, '0', 0) > 0) {
594.  594                     $temp = bcmod($current, '16777216');
595.  595                     $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
596.  596                     $current = bcdiv($current, '16777216', 0);
597.  597                 }
598.  598 
599.  599                 return $this->precision > 0 ?
600.  600                     substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
601.  601                     ltrim($value, chr(0));
602.  602         }
603.  603 
604.  604         if (!count($this->value)) {
605.  605             return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
606.  606         }
607.  607         $result = $this->_int2bytes($this->value[count($this->value) - 1]);
608.  608 
609.  609         $temp = $this->copy();
610.  610 
611.  611         for ($i = count($temp->value) - 2; $i >= 0; --$i) {
612.  612             $temp->_base256_lshift($result, MATH_BIGINTEGER_BASE);
613.  613             $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
614.  614         }
615.  615 
616.  616         return $this->precision > 0 ?
617.  617             str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
618.  618             $result;
619.  619     }
620.  620 
621.  621     /**
622.  622      * Converts a BigInteger to a hex string (eg. base-16)).
623.  623      *
624.  624      * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
625.  625      * saved as two's compliment.
626.  626      *
627.  627      * Here's an example:
628.  628      * <code>
629.  629      * <?php
630.  630      *    include 'Math/BigInteger.php';
631.  631      *
632.  632      *    $a = new Math_BigInteger('65');
633.  633      *
634.  634      *    echo $a->toHex(); // outputs '41'
635.  635      * ?>
636.  636      * </code>
637.  637      *
638.  638      * @param bool $twos_compliment
639.  639      * @return string
640.  640      * @access public
641.  641      * @internal Converts a base-2**26 number to base-2**8
642.  642      */
643.  643     function toHex($twos_compliment = false)
644.  644     {
645.  645         return bin2hex($this->toBytes($twos_compliment));
646.  646     }
647.  647 
648.  648     /**
649.  649      * Converts a BigInteger to a bit string (eg. base-2).
650.  650      *
651.  651      * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
652.  652      * saved as two's compliment.
653.  653      *
654.  654      * Here's an example:
655.  655      * <code>
656.  656      * <?php
657.  657      *    include 'Math/BigInteger.php';
658.  658      *
659.  659      *    $a = new Math_BigInteger('65');
660.  660      *
661.  661      *    echo $a->toBits(); // outputs '1000001'
662.  662      * ?>
663.  663      * </code>
664.  664      *
665.  665      * @param bool $twos_compliment
666.  666      * @return string
667.  667      * @access public
668.  668      * @internal Converts a base-2**26 number to base-2**2
669.  669      */
670.  670     function toBits($twos_compliment = false)
671.  671     {
672.  672         $hex = $this->toHex($twos_compliment);
673.  673         $bits = '';
674.  674         for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
675.  675             $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits;
676.  676         }
677.  677         if ($start) { // hexdec('') == 0
678.  678             $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits;
679.  679         }
680.  680         $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
681.  681 
682.  682         if ($twos_compliment && $this->compare(new Math_BigInteger()) > 0 && $this->precision <= 0) {
683.  683             return '0' . $result;
684.  684         }
685.  685 
686.  686         return $result;
687.  687     }
688.  688 
689.  689     /**
690.  690      * Converts a BigInteger to a base-10 number.
691.  691      *
692.  692      * Here's an example:
693.  693      * <code>
694.  694      * <?php
695.  695      *    include 'Math/BigInteger.php';
696.  696      *
697.  697      *    $a = new Math_BigInteger('50');
698.  698      *
699.  699      *    echo $a->toString(); // outputs 50
700.  700      * ?>
701.  701      * </code>
702.  702      *
703.  703      * @return string
704.  704      * @access public
705.  705      * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
706.  706      */
707.  707     function toString()
708.  708     {
709.  709         switch (MATH_BIGINTEGER_MODE) {
710.  710             case MATH_BIGINTEGER_MODE_GMP:
711.  711                 return gmp_strval($this->value);
712.  712             case MATH_BIGINTEGER_MODE_BCMATH:
713.  713                 if ($this->value === '0') {
714.  714                     return '0';
715.  715                 }
716.  716 
717.  717                 return ltrim($this->value, '0');
718.  718         }
719.  719 
720.  720         if (!count($this->value)) {
721.  721             return '0';
722.  722         }
723.  723 
724.  724         $temp = $this->copy();
725.  725         $temp->is_negative = false;
726.  726 
727.  727         $divisor = new Math_BigInteger();
728.  728         $divisor->value = array(MATH_BIGINTEGER_MAX10);
729.  729         $result = '';
730.  730         while (count($temp->value)) {
731.  731             list($temp, $mod) = $temp->divide($divisor);
732.  732             $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', MATH_BIGINTEGER_MAX10_LEN, '0', STR_PAD_LEFT) . $result;
733.  733         }
734.  734         $result = ltrim($result, '0');
735.  735         if (empty($result)) {
736.  736             $result = '0';
737.  737         }
738.  738 
739.  739         if ($this->is_negative) {
740.  740             $result = '-' . $result;
741.  741         }
742.  742 
743.  743         return $result;
744.  744     }
745.  745 
746.  746     /**
747.  747      * Copy an object
748.  748      *
749.  749      * PHP5 passes objects by reference while PHP4 passes by value.  As such, we need a function to guarantee
750.  750      * that all objects are passed by value, when appropriate.  More information can be found here:
751.  751      *
752.  752      * {@link http://php.net/language.oop5.basic#51624}
753.  753      *
754.  754      * @access public
755.  755      * @see self::__clone()
756.  756      * @return Math_BigInteger
757.  757      */
758.  758     function copy()
759.  759     {
760.  760         $temp = new Math_BigInteger();
761.  761         $temp->value = $this->value;
762.  762         $temp->is_negative = $this->is_negative;
763.  763         $temp->precision = $this->precision;
764.  764         $temp->bitmask = $this->bitmask;
765.  765         return $temp;
766.  766     }
767.  767 
768.  768     /**
769.  769      *  __toString() magic method
770.  770      *
771.  771      * Will be called, automatically, if you're supporting just PHP5.  If you're supporting PHP4, you'll need to call
772.  772      * toString().
773.  773      *
774.  774      * @access public
775.  775      * @internal Implemented per a suggestion by Techie-Michael - thanks!
776.  776      */
777.  777     function __toString()
778.  778     {
779.  779         return $this->toString();
780.  780     }
781.  781 
782.  782     /**
783.  783      * __clone() magic method
784.  784      *
785.  785      * Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone()
786.  786      * directly in PHP5.  You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5
787.  787      * only syntax of $y = clone $x.  As such, if you're trying to write an application that works on both PHP4 and PHP5,
788.  788      * call Math_BigInteger::copy(), instead.
789.  789      *
790.  790      * @access public
791.  791      * @see self::copy()
792.  792      * @return Math_BigInteger
793.  793      */
794.  794     function __clone()
795.  795     {
796.  796         return $this->copy();
797.  797     }
798.  798 
799.  799     /**
800.  800      *  __sleep() magic method
801.  801      *
802.  802      * Will be called, automatically, when serialize() is called on a Math_BigInteger object.
803.  803      *
804.  804      * @see self::__wakeup()
805.  805      * @access public
806.  806      */
807.  807     function __sleep()
808.  808     {
809.  809         $this->hex = $this->toHex(true);
810.  810         $vars = array('hex');
811.  811         if ($this->precision > 0) {
812.  812             $vars[] = 'precision';
813.  813         }
814.  814         return $vars;
815.  815     }
816.  816 
817.  817     /**
818.  818      *  __wakeup() magic method
819.  819      *
820.  820      * Will be called, automatically, when unserialize() is called on a Math_BigInteger object.
821.  821      *
822.  822      * @see self::__sleep()
823.  823      * @access public
824.  824      */
825.  825     function __wakeup()
826.  826     {
827.  827         $temp = new Math_BigInteger($this->hex, -16);
828.  828         $this->value = $temp->value;
829.  829         $this->is_negative = $temp->is_negative;
830.  830         if ($this->precision > 0) {
831.  831             // recalculate $this->bitmask
832.  832             $this->setPrecision($this->precision);
833.  833         }
834.  834     }
835.  835 
836.  836     /**
837.  837      *  __debugInfo() magic method
838.  838      *
839.  839      * Will be called, automatically, when print_r() or var_dump() are called
840.  840      *
841.  841      * @access public
842.  842      */
843.  843     function __debugInfo()
844.  844     {
845.  845         $opts = array();
846.  846         switch (MATH_BIGINTEGER_MODE) {
847.  847             case MATH_BIGINTEGER_MODE_GMP:
848.  848                 $engine = 'gmp';
849.  849                 break;
850.  850             case MATH_BIGINTEGER_MODE_BCMATH:
851.  851                 $engine = 'bcmath';
852.  852                 break;
853.  853             case MATH_BIGINTEGER_MODE_INTERNAL:
854.  854                 $engine = 'internal';
855.  855                 $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit';
856.  856         }
857.  857         if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
858.  858             $opts[] = 'OpenSSL';
859.  859         }
860.  860         if (!empty($opts)) {
861.  861             $engine.= ' (' . implode($opts, ', ') . ')';
862.  862         }
863.  863         return array(
864.  864             'value' => '0x' . $this->toHex(true),
865.  865             'engine' => $engine
866.  866         );
867.  867     }
868.  868 
869.  869     /**
870.  870      * Adds two BigIntegers.
871.  871      *
872.  872      * Here's an example:
873.  873      * <code>
874.  874      * <?php
875.  875      *    include 'Math/BigInteger.php';
876.  876      *
877.  877      *    $a = new Math_BigInteger('10');
878.  878      *    $b = new Math_BigInteger('20');
879.  879      *
880.  880      *    $c = $a->add($b);
881.  881      *
882.  882      *    echo $c->toString(); // outputs 30
883.  883      * ?>
884.  884      * </code>
885.  885      *
886.  886      * @param Math_BigInteger $y
887.  887      * @return Math_BigInteger
888.  888      * @access public
889.  889      * @internal Performs base-2**52 addition
890.  890      */
891.  891     function add($y)
892.  892     {
893.  893         switch (MATH_BIGINTEGER_MODE) {
894.  894             case MATH_BIGINTEGER_MODE_GMP:
895.  895                 $temp = new Math_BigInteger();
896.  896                 $temp->value = gmp_add($this->value, $y->value);
897.  897 
898.  898                 return $this->_normalize($temp);
899.  899             case MATH_BIGINTEGER_MODE_BCMATH:
900.  900                 $temp = new Math_BigInteger();
901.  901                 $temp->value = bcadd($this->value, $y->value, 0);
902.  902 
903.  903                 return $this->_normalize($temp);
904.  904         }
905.  905 
906.  906         $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
907.  907 
908.  908         $result = new Math_BigInteger();
909.  909         $result->value = $temp[MATH_BIGINTEGER_VALUE];
910.  910         $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
911.  911 
912.  912         return $this->_normalize($result);
913.  913     }
914.  914 
915.  915     /**
916.  916      * Performs addition.
917.  917      *
918.  918      * @param array $x_value
919.  919      * @param bool $x_negative
920.  920      * @param array $y_value
921.  921      * @param bool $y_negative
922.  922      * @return array
923.  923      * @access private
924.  924      */
925.  925     function _add($x_value, $x_negative, $y_value, $y_negative)
926.  926     {
927.  927         $x_size = count($x_value);
928.  928         $y_size = count($y_value);
929.  929 
930.  930         if ($x_size == 0) {
931.  931             return array(
932.  932                 MATH_BIGINTEGER_VALUE => $y_value,
933.  933                 MATH_BIGINTEGER_SIGN => $y_negative
934.  934             );
935.  935         } elseif ($y_size == 0) {
936.  936             return array(
937.  937                 MATH_BIGINTEGER_VALUE => $x_value,
938.  938                 MATH_BIGINTEGER_SIGN => $x_negative
939.  939             );
940.  940         }
941.  941 
942.  942         // subtract, if appropriate
943.  943         if ($x_negative != $y_negative) {
944.  944             if ($x_value == $y_value) {
945.  945                 return array(
946.  946                     MATH_BIGINTEGER_VALUE => array(),
947.  947                     MATH_BIGINTEGER_SIGN => false
948.  948                 );
949.  949             }
950.  950 
951.  951             $temp = $this->_subtract($x_value, false, $y_value, false);
952.  952             $temp[MATH_BIGINTEGER_SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
953.  953                                           $x_negative : $y_negative;
954.  954 
955.  955             return $temp;
956.  956         }
957.  957 
958.  958         if ($x_size < $y_size) {
959.  959             $size = $x_size;
960.  960             $value = $y_value;
961.  961         } else {
962.  962             $size = $y_size;
963.  963             $value = $x_value;
964.  964         }
965.  965 
966.  966         $value[count($value)] = 0; // just in case the carry adds an extra digit
967.  967 
968.  968         $carry = 0;
969.  969         for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
970.  970             $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] + $y_value[$j] * MATH_BIGINTEGER_BASE_FULL + $y_value[$i] + $carry;
971.  971             $carry = $sum >= MATH_BIGINTEGER_MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
972.  972             $sum = $carry ? $sum - MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
973.  973 
974.  974             $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
975.  975 
976.  976             $value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
977.  977             $value[$j] = $temp;
978.  978         }
979.  979 
980.  980         if ($j == $size) { // ie. if $y_size is odd
981.  981             $sum = $x_value[$i] + $y_value[$i] + $carry;
982.  982             $carry = $sum >= MATH_BIGINTEGER_BASE_FULL;
983.  983             $value[$i] = $carry ? $sum - MATH_BIGINTEGER_BASE_FULL : $sum;
984.  984             ++$i; // ie. let $i = $j since we've just done $value[$i]
985.  985         }
986.  986 
987.  987         if ($carry) {
988.  988             for (; $value[$i] == MATH_BIGINTEGER_MAX_DIGIT; ++$i) {
989.  989                 $value[$i] = 0;
990.  990             }
991.  991             ++$value[$i];
992.  992         }
993.  993 
994.  994         return array(
995.  995             MATH_BIGINTEGER_VALUE => $this->_trim($value),
996.  996             MATH_BIGINTEGER_SIGN => $x_negative
997.  997         );
998.  998     }
999.  999 
1000. 1000     /**
1001. 1001      * Subtracts two BigIntegers.
1002. 1002      *
1003. 1003      * Here's an example:
1004. 1004      * <code>
1005. 1005      * <?php
1006. 1006      *    include 'Math/BigInteger.php';
1007. 1007      *
1008. 1008      *    $a = new Math_BigInteger('10');
1009. 1009      *    $b = new Math_BigInteger('20');
1010. 1010      *
1011. 1011      *    $c = $a->subtract($b);
1012. 1012      *
1013. 1013      *    echo $c->toString(); // outputs -10
1014. 1014      * ?>
1015. 1015      * </code>
1016. 1016      *
1017. 1017      * @param Math_BigInteger $y
1018. 1018      * @return Math_BigInteger
1019. 1019      * @access public
1020. 1020      * @internal Performs base-2**52 subtraction
1021. 1021      */
1022. 1022     function subtract($y)
1023. 1023     {
1024. 1024         switch (MATH_BIGINTEGER_MODE) {
1025. 1025             case MATH_BIGINTEGER_MODE_GMP:
1026. 1026                 $temp = new Math_BigInteger();
1027. 1027                 $temp->value = gmp_sub($this->value, $y->value);
1028. 1028 
1029. 1029                 return $this->_normalize($temp);
1030. 1030             case MATH_BIGINTEGER_MODE_BCMATH:
1031. 1031                 $temp = new Math_BigInteger();
1032. 1032                 $temp->value = bcsub($this->value, $y->value, 0);
1033. 1033 
1034. 1034                 return $this->_normalize($temp);
1035. 1035         }
1036. 1036 
1037. 1037         $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
1038. 1038 
1039. 1039         $result = new Math_BigInteger();
1040. 1040         $result->value = $temp[MATH_BIGINTEGER_VALUE];
1041. 1041         $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
1042. 1042 
1043. 1043         return $this->_normalize($result);
1044. 1044     }
1045. 1045 
1046. 1046     /**
1047. 1047      * Performs subtraction.
1048. 1048      *
1049. 1049      * @param array $x_value
1050. 1050      * @param bool $x_negative
1051. 1051      * @param array $y_value
1052. 1052      * @param bool $y_negative
1053. 1053      * @return array
1054. 1054      * @access private
1055. 1055      */
1056. 1056     function _subtract($x_value, $x_negative, $y_value, $y_negative)
1057. 1057     {
1058. 1058         $x_size = count($x_value);
1059. 1059         $y_size = count($y_value);
1060. 1060 
1061. 1061         if ($x_size == 0) {
1062. 1062             return array(
1063. 1063                 MATH_BIGINTEGER_VALUE => $y_value,
1064. 1064                 MATH_BIGINTEGER_SIGN => !$y_negative
1065. 1065             );
1066. 1066         } elseif ($y_size == 0) {
1067. 1067             return array(
1068. 1068                 MATH_BIGINTEGER_VALUE => $x_value,
1069. 1069                 MATH_BIGINTEGER_SIGN => $x_negative
1070. 1070             );
1071. 1071         }
1072. 1072 
1073. 1073         // add, if appropriate (ie. -$x - +$y or +$x - -$y)
1074. 1074         if ($x_negative != $y_negative) {
1075. 1075             $temp = $this->_add($x_value, false, $y_value, false);
1076. 1076             $temp[MATH_BIGINTEGER_SIGN] = $x_negative;
1077. 1077 
1078. 1078             return $temp;
1079. 1079         }
1080. 1080 
1081. 1081         $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
1082. 1082 
1083. 1083         if (!$diff) {
1084. 1084             return array(
1085. 1085                 MATH_BIGINTEGER_VALUE => array(),
1086. 1086                 MATH_BIGINTEGER_SIGN => false
1087. 1087             );
1088. 1088         }
1089. 1089 
1090. 1090         // switch $x and $y around, if appropriate.
1091. 1091         if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
1092. 1092             $temp = $x_value;
1093. 1093             $x_value = $y_value;
1094. 1094             $y_value = $temp;
1095. 1095 
1096. 1096             $x_negative = !$x_negative;
1097. 1097 
1098. 1098             $x_size = count($x_value);
1099. 1099             $y_size = count($y_value);
1100. 1100         }
1101. 1101 
1102. 1102         // at this point, $x_value should be at least as big as - if not bigger than - $y_value
1103. 1103 
1104. 1104         $carry = 0;
1105. 1105         for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
1106. 1106             $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] - $y_value[$j] * MATH_BIGINTEGER_BASE_FULL - $y_value[$i] - $carry;
1107. 1107             $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
1108. 1108             $sum = $carry ? $sum + MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
1109. 1109 
1110. 1110             $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
1111. 1111 
1112. 1112             $x_value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp);
1113. 1113             $x_value[$j] = $temp;
1114. 1114         }
1115. 1115 
1116. 1116         if ($j == $y_size) { // ie. if $y_size is odd
1117. 1117             $sum = $x_value[$i] - $y_value[$i] - $carry;
1118. 1118             $carry = $sum < 0;
1119. 1119             $x_value[$i] = $carry ? $sum + MATH_BIGINTEGER_BASE_FULL : $sum;
1120. 1120             ++$i;
1121. 1121         }
1122. 1122 
1123. 1123         if ($carry) {
1124. 1124             for (; !$x_value[$i]; ++$i) {
1125. 1125                 $x_value[$i] = MATH_BIGINTEGER_MAX_DIGIT;
1126. 1126             }
1127. 1127             --$x_value[$i];
1128. 1128         }
1129. 1129 
1130. 1130         return array(
1131. 1131             MATH_BIGINTEGER_VALUE => $this->_trim($x_value),
1132. 1132             MATH_BIGINTEGER_SIGN => $x_negative
1133. 1133         );
1134. 1134     }
1135. 1135 
1136. 1136     /**
1137. 1137      * Multiplies two BigIntegers
1138. 1138      *
1139. 1139      * Here's an example:
1140. 1140      * <code>
1141. 1141      * <?php
1142. 1142      *    include 'Math/BigInteger.php';
1143. 1143      *
1144. 1144      *    $a = new Math_BigInteger('10');
1145. 1145      *    $b = new Math_BigInteger('20');
1146. 1146      *
1147. 1147      *    $c = $a->multiply($b);
1148. 1148      *
1149. 1149      *    echo $c->toString(); // outputs 200
1150. 1150      * ?>
1151. 1151      * </code>
1152. 1152      *
1153. 1153      * @param Math_BigInteger $x
1154. 1154      * @return Math_BigInteger
1155. 1155      * @access public
1156. 1156      */
1157. 1157     function multiply($x)
1158. 1158     {
1159. 1159         switch (MATH_BIGINTEGER_MODE) {
1160. 1160             case MATH_BIGINTEGER_MODE_GMP:
1161. 1161                 $temp = new Math_BigInteger();
1162. 1162                 $temp->value = gmp_mul($this->value, $x->value);
1163. 1163 
1164. 1164                 return $this->_normalize($temp);
1165. 1165             case MATH_BIGINTEGER_MODE_BCMATH:
1166. 1166                 $temp = new Math_BigInteger();
1167. 1167                 $temp->value = bcmul($this->value, $x->value, 0);
1168. 1168 
1169. 1169                 return $this->_normalize($temp);
1170. 1170         }
1171. 1171 
1172. 1172         $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
1173. 1173 
1174. 1174         $product = new Math_BigInteger();
1175. 1175         $product->value = $temp[MATH_BIGINTEGER_VALUE];
1176. 1176         $product->is_negative = $temp[MATH_BIGINTEGER_SIGN];
1177. 1177 
1178. 1178         return $this->_normalize($product);
1179. 1179     }
1180. 1180 
1181. 1181     /**
1182. 1182      * Performs multiplication.
1183. 1183      *
1184. 1184      * @param array $x_value
1185. 1185      * @param bool $x_negative
1186. 1186      * @param array $y_value
1187. 1187      * @param bool $y_negative
1188. 1188      * @return array
1189. 1189      * @access private
1190. 1190      */
1191. 1191     function _multiply($x_value, $x_negative, $y_value, $y_negative)
1192. 1192     {
1193. 1193         //if ( $x_value == $y_value ) {
1194. 1194         //    return array(
1195. 1195         //        MATH_BIGINTEGER_VALUE => $this->_square($x_value),
1196. 1196         //        MATH_BIGINTEGER_SIGN => $x_sign != $y_value
1197. 1197         //    );
1198. 1198         //}
1199. 1199 
1200. 1200         $x_length = count($x_value);
1201. 1201         $y_length = count($y_value);
1202. 1202 
1203. 1203         if (!$x_length || !$y_length) { // a 0 is being multiplied
1204. 1204             return array(
1205. 1205                 MATH_BIGINTEGER_VALUE => array(),
1206. 1206                 MATH_BIGINTEGER_SIGN => false
1207. 1207             );
1208. 1208         }
1209. 1209 
1210. 1210         return array(
1211. 1211             MATH_BIGINTEGER_VALUE => min($x_length, $y_length) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
1212. 1212                 $this->_trim($this->_regularMultiply($x_value, $y_value)) :
1213. 1213                 $this->_trim($this->_karatsuba($x_value, $y_value)),
1214. 1214             MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
1215. 1215         );
1216. 1216     }
1217. 1217 
1218. 1218     /**
1219. 1219      * Performs long multiplication on two BigIntegers
1220. 1220      *
1221. 1221      * Modeled after 'multiply' in MutableBigInteger.java.
1222. 1222      *
1223. 1223      * @param array $x_value
1224. 1224      * @param array $y_value
1225. 1225      * @return array
1226. 1226      * @access private
1227. 1227      */
1228. 1228     function _regularMultiply($x_value, $y_value)
1229. 1229     {
1230. 1230         $x_length = count($x_value);
1231. 1231         $y_length = count($y_value);
1232. 1232 
1233. 1233         if (!$x_length || !$y_length) { // a 0 is being multiplied
1234. 1234             return array();
1235. 1235         }
1236. 1236 
1237. 1237         if ($x_length < $y_length) {
1238. 1238             $temp = $x_value;
1239. 1239             $x_value = $y_value;
1240. 1240             $y_value = $temp;
1241. 1241 
1242. 1242             $x_length = count($x_value);
1243. 1243             $y_length = count($y_value);
1244. 1244         }
1245. 1245 
1246. 1246         $product_value = $this->_array_repeat(0, $x_length + $y_length);
1247. 1247 
1248. 1248         // the following for loop could be removed if the for loop following it
1249. 1249         // (the one with nested for loops) initially set $i to 0, but
1250. 1250         // doing so would also make the result in one set of unnecessary adds,
1251. 1251         // since on the outermost loops first pass, $product->value[$k] is going
1252. 1252         // to always be 0
1253. 1253 
1254. 1254         $carry = 0;
1255. 1255 
1256. 1256         for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
1257. 1257             $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
1258. 1258             $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1259. 1259             $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
1260. 1260         }
1261. 1261 
1262. 1262         $product_value[$j] = $carry;
1263. 1263 
1264. 1264         // the above for loop is what the previous comment was talking about.  the
1265. 1265         // following for loop is the "one with nested for loops"
1266. 1266         for ($i = 1; $i < $y_length; ++$i) {
1267. 1267             $carry = 0;
1268. 1268 
1269. 1269             for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
1270. 1270                 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
1271. 1271                 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1272. 1272                 $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
1273. 1273             }
1274. 1274 
1275. 1275             $product_value[$k] = $carry;
1276. 1276         }
1277. 1277 
1278. 1278         return $product_value;
1279. 1279     }
1280. 1280 
1281. 1281     /**
1282. 1282      * Performs Karatsuba multiplication on two BigIntegers
1283. 1283      *
1284. 1284      * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1285. 1285      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
1286. 1286      *
1287. 1287      * @param array $x_value
1288. 1288      * @param array $y_value
1289. 1289      * @return array
1290. 1290      * @access private
1291. 1291      */
1292. 1292     function _karatsuba($x_value, $y_value)
1293. 1293     {
1294. 1294         $m = min(count($x_value) >> 1, count($y_value) >> 1);
1295. 1295 
1296. 1296         if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
1297. 1297             return $this->_regularMultiply($x_value, $y_value);
1298. 1298         }
1299. 1299 
1300. 1300         $x1 = array_slice($x_value, $m);
1301. 1301         $x0 = array_slice($x_value, 0, $m);
1302. 1302         $y1 = array_slice($y_value, $m);
1303. 1303         $y0 = array_slice($y_value, 0, $m);
1304. 1304 
1305. 1305         $z2 = $this->_karatsuba($x1, $y1);
1306. 1306         $z0 = $this->_karatsuba($x0, $y0);
1307. 1307 
1308. 1308         $z1 = $this->_add($x1, false, $x0, false);
1309. 1309         $temp = $this->_add($y1, false, $y0, false);
1310. 1310         $z1 = $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_VALUE]);
1311. 1311         $temp = $this->_add($z2, false, $z0, false);
1312. 1312         $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
1313. 1313 
1314. 1314         $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1315. 1315         $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
1316. 1316 
1317. 1317         $xy = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
1318. 1318         $xy = $this->_add($xy[MATH_BIGINTEGER_VALUE], $xy[MATH_BIGINTEGER_SIGN], $z0, false);
1319. 1319 
1320. 1320         return $xy[MATH_BIGINTEGER_VALUE];
1321. 1321     }
1322. 1322 
1323. 1323     /**
1324. 1324      * Performs squaring
1325. 1325      *
1326. 1326      * @param array $x
1327. 1327      * @return array
1328. 1328      * @access private
1329. 1329      */
1330. 1330     function _square($x = false)
1331. 1331     {
1332. 1332         return count($x) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
1333. 1333             $this->_trim($this->_baseSquare($x)) :
1334. 1334             $this->_trim($this->_karatsubaSquare($x));
1335. 1335     }
1336. 1336 
1337. 1337     /**
1338. 1338      * Performs traditional squaring on two BigIntegers
1339. 1339      *
1340. 1340      * Squaring can be done faster than multiplying a number by itself can be.  See
1341. 1341      * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
1342. 1342      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
1343. 1343      *
1344. 1344      * @param array $value
1345. 1345      * @return array
1346. 1346      * @access private
1347. 1347      */
1348. 1348     function _baseSquare($value)
1349. 1349     {
1350. 1350         if (empty($value)) {
1351. 1351             return array();
1352. 1352         }
1353. 1353         $square_value = $this->_array_repeat(0, 2 * count($value));
1354. 1354 
1355. 1355         for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
1356. 1356             $i2 = $i << 1;
1357. 1357 
1358. 1358             $temp = $square_value[$i2] + $value[$i] * $value[$i];
1359. 1359             $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1360. 1360             $square_value[$i2] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
1361. 1361 
1362. 1362             // note how we start from $i+1 instead of 0 as we do in multiplication.
1363. 1363             for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
1364. 1364                 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
1365. 1365                 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1366. 1366                 $square_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
1367. 1367             }
1368. 1368 
1369. 1369             // the following line can yield values larger 2**15.  at this point, PHP should switch
1370. 1370             // over to floats.
1371. 1371             $square_value[$i + $max_index + 1] = $carry;
1372. 1372         }
1373. 1373 
1374. 1374         return $square_value;
1375. 1375     }
1376. 1376 
1377. 1377     /**
1378. 1378      * Performs Karatsuba "squaring" on two BigIntegers
1379. 1379      *
1380. 1380      * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1381. 1381      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
1382. 1382      *
1383. 1383      * @param array $value
1384. 1384      * @return array
1385. 1385      * @access private
1386. 1386      */
1387. 1387     function _karatsubaSquare($value)
1388. 1388     {
1389. 1389         $m = count($value) >> 1;
1390. 1390 
1391. 1391         if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
1392. 1392             return $this->_baseSquare($value);
1393. 1393         }
1394. 1394 
1395. 1395         $x1 = array_slice($value, $m);
1396. 1396         $x0 = array_slice($value, 0, $m);
1397. 1397 
1398. 1398         $z2 = $this->_karatsubaSquare($x1);
1399. 1399         $z0 = $this->_karatsubaSquare($x0);
1400. 1400 
1401. 1401         $z1 = $this->_add($x1, false, $x0, false);
1402. 1402         $z1 = $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE]);
1403. 1403         $temp = $this->_add($z2, false, $z0, false);
1404. 1404         $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
1405. 1405 
1406. 1406         $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1407. 1407         $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
1408. 1408 
1409. 1409         $xx = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
1410. 1410         $xx = $this->_add($xx[MATH_BIGINTEGER_VALUE], $xx[MATH_BIGINTEGER_SIGN], $z0, false);
1411. 1411 
1412. 1412         return $xx[MATH_BIGINTEGER_VALUE];
1413. 1413     }
1414. 1414 
1415. 1415     /**
1416. 1416      * Divides two BigIntegers.
1417. 1417      *
1418. 1418      * Returns an array whose first element contains the quotient and whose second element contains the
1419. 1419      * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
1420. 1420      * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
1421. 1421      * and the divisor (basically, the "common residue" is the first positive modulo).
1422. 1422      *
1423. 1423      * Here's an example:
1424. 1424      * <code>
1425. 1425      * <?php
1426. 1426      *    include 'Math/BigInteger.php';
1427. 1427      *
1428. 1428      *    $a = new Math_BigInteger('10');
1429. 1429      *    $b = new Math_BigInteger('20');
1430. 1430      *
1431. 1431      *    list($quotient, $remainder) = $a->divide($b);
1432. 1432      *
1433. 1433      *    echo $quotient->toString(); // outputs 0
1434. 1434      *    echo "\r\n";
1435. 1435      *    echo $remainder->toString(); // outputs 10
1436. 1436      * ?>
1437. 1437      * </code>
1438. 1438      *
1439. 1439      * @param Math_BigInteger $y
1440. 1440      * @return array
1441. 1441      * @access public
1442. 1442      * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
1443. 1443      */
1444. 1444     function divide($y)
1445. 1445     {
1446. 1446         switch (MATH_BIGINTEGER_MODE) {
1447. 1447             case MATH_BIGINTEGER_MODE_GMP:
1448. 1448                 $quotient = new Math_BigInteger();
1449. 1449                 $remainder = new Math_BigInteger();
1450. 1450 
1451. 1451                 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
1452. 1452 
1453. 1453                 if (gmp_sign($remainder->value) < 0) {
1454. 1454                     $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
1455. 1455                 }
1456. 1456 
1457. 1457                 return array($this->_normalize($quotient), $this->_normalize($remainder));
1458. 1458             case MATH_BIGINTEGER_MODE_BCMATH:
1459. 1459                 $quotient = new Math_BigInteger();
1460. 1460                 $remainder = new Math_BigInteger();
1461. 1461 
1462. 1462                 $quotient->value = bcdiv($this->value, $y->value, 0);
1463. 1463                 $remainder->value = bcmod($this->value, $y->value);
1464. 1464 
1465. 1465                 if ($remainder->value[0] == '-') {
1466. 1466                     $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
1467. 1467                 }
1468. 1468 
1469. 1469                 return array($this->_normalize($quotient), $this->_normalize($remainder));
1470. 1470         }
1471. 1471 
1472. 1472         if (count($y->value) == 1) {
1473. 1473             list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
1474. 1474             $quotient = new Math_BigInteger();
1475. 1475             $remainder = new Math_BigInteger();
1476. 1476             $quotient->value = $q;
1477. 1477             $remainder->value = array($r);
1478. 1478             $quotient->is_negative = $this->is_negative != $y->is_negative;
1479. 1479             return array($this->_normalize($quotient), $this->_normalize($remainder));
1480. 1480         }
1481. 1481 
1482. 1482         static $zero;
1483. 1483         if (!isset($zero)) {
1484. 1484             $zero = new Math_BigInteger();
1485. 1485         }
1486. 1486 
1487. 1487         $x = $this->copy();
1488. 1488         $y = $y->copy();
1489. 1489 
1490. 1490         $x_sign = $x->is_negative;
1491. 1491         $y_sign = $y->is_negative;
1492. 1492 
1493. 1493         $x->is_negative = $y->is_negative = false;
1494. 1494 
1495. 1495         $diff = $x->compare($y);
1496. 1496 
1497. 1497         if (!$diff) {
1498. 1498             $temp = new Math_BigInteger();
1499. 1499             $temp->value = array(1);
1500. 1500             $temp->is_negative = $x_sign != $y_sign;
1501. 1501             return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger()));
1502. 1502         }
1503. 1503 
1504. 1504         if ($diff < 0) {
1505. 1505             // if $x is negative, "add" $y.
1506. 1506             if ($x_sign) {
1507. 1507                 $x = $y->subtract($x);
1508. 1508             }
1509. 1509             return array($this->_normalize(new Math_BigInteger()), $this->_normalize($x));
1510. 1510         }
1511. 1511 
1512. 1512         // normalize $x and $y as described in HAC 14.23 / 14.24
1513. 1513         $msb = $y->value[count($y->value) - 1];
1514. 1514         for ($shift = 0; !($msb & MATH_BIGINTEGER_MSB); ++$shift) {
1515. 1515             $msb <<= 1;
1516. 1516         }
1517. 1517         $x->_lshift($shift);
1518. 1518         $y->_lshift($shift);
1519. 1519         $y_value = &$y->value;
1520. 1520 
1521. 1521         $x_max = count($x->value) - 1;
1522. 1522         $y_max = count($y->value) - 1;
1523. 1523 
1524. 1524         $quotient = new Math_BigInteger();
1525. 1525         $quotient_value = &$quotient->value;
1526. 1526         $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
1527. 1527 
1528. 1528         static $temp, $lhs, $rhs;
1529. 1529         if (!isset($temp)) {
1530. 1530             $temp = new Math_BigInteger();
1531. 1531             $lhs =  new Math_BigInteger();
1532. 1532             $rhs =  new Math_BigInteger();
1533. 1533         }
1534. 1534         $temp_value = &$temp->value;
1535. 1535         $rhs_value =  &$rhs->value;
1536. 1536 
1537. 1537         // $temp = $y << ($x_max - $y_max-1) in base 2**26
1538. 1538         $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
1539. 1539 
1540. 1540         while ($x->compare($temp) >= 0) {
1541. 1541             // calculate the "common residue"
1542. 1542             ++$quotient_value[$x_max - $y_max];
1543. 1543             $x = $x->subtract($temp);
1544. 1544             $x_max = count($x->value) - 1;
1545. 1545         }
1546. 1546 
1547. 1547         for ($i = $x_max; $i >= $y_max + 1; --$i) {
1548. 1548             $x_value = &$x->value;
1549. 1549             $x_window = array(
1550. 1550                 isset($x_value[$i]) ? $x_value[$i] : 0,
1551. 1551                 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
1552. 1552                 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
1553. 1553             );
1554. 1554             $y_window = array(
1555. 1555                 $y_value[$y_max],
1556. 1556                 ($y_max > 0) ? $y_value[$y_max - 1] : 0
1557. 1557             );
1558. 1558 
1559. 1559             $q_index = $i - $y_max - 1;
1560. 1560             if ($x_window[0] == $y_window[0]) {
1561. 1561                 $quotient_value[$q_index] = MATH_BIGINTEGER_MAX_DIGIT;
1562. 1562             } else {
1563. 1563                 $quotient_value[$q_index] = $this->_safe_divide(
1564. 1564                     $x_window[0] * MATH_BIGINTEGER_BASE_FULL + $x_window[1],
1565. 1565                     $y_window[0]
1566. 1566                 );
1567. 1567             }
1568. 1568 
1569. 1569             $temp_value = array($y_window[1], $y_window[0]);
1570. 1570 
1571. 1571             $lhs->value = array($quotient_value[$q_index]);
1572. 1572             $lhs = $lhs->multiply($temp);
1573. 1573 
1574. 1574             $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
1575. 1575 
1576. 1576             while ($lhs->compare($rhs) > 0) {
1577. 1577                 --$quotient_value[$q_index];
1578. 1578 
1579. 1579                 $lhs->value = array($quotient_value[$q_index]);
1580. 1580                 $lhs = $lhs->multiply($temp);
1581. 1581             }
1582. 1582 
1583. 1583             $adjust = $this->_array_repeat(0, $q_index);
1584. 1584             $temp_value = array($quotient_value[$q_index]);
1585. 1585             $temp = $temp->multiply($y);
1586. 1586             $temp_value = &$temp->value;
1587. 1587             $temp_value = array_merge($adjust, $temp_value);
1588. 1588 
1589. 1589             $x = $x->subtract($temp);
1590. 1590 
1591. 1591             if ($x->compare($zero) < 0) {
1592. 1592                 $temp_value = array_merge($adjust, $y_value);
1593. 1593                 $x = $x->add($temp);
1594. 1594 
1595. 1595                 --$quotient_value[$q_index];
1596. 1596             }
1597. 1597 
1598. 1598             $x_max = count($x_value) - 1;
1599. 1599         }
1600. 1600 
1601. 1601         // unnormalize the remainder
1602. 1602         $x->_rshift($shift);
1603. 1603 
1604. 1604         $quotient->is_negative = $x_sign != $y_sign;
1605. 1605 
1606. 1606         // calculate the "common residue", if appropriate
1607. 1607         if ($x_sign) {
1608. 1608             $y->_rshift($shift);
1609. 1609             $x = $y->subtract($x);
1610. 1610         }
1611. 1611 
1612. 1612         return array($this->_normalize($quotient), $this->_normalize($x));
1613. 1613     }
1614. 1614 
1615. 1615     /**
1616. 1616      * Divides a BigInteger by a regular integer
1617. 1617      *
1618. 1618      * abc / x = a00 / x + b0 / x + c / x
1619. 1619      *
1620. 1620      * @param array $dividend
1621. 1621      * @param array $divisor
1622. 1622      * @return array
1623. 1623      * @access private
1624. 1624      */
1625. 1625     function _divide_digit($dividend, $divisor)
1626. 1626     {
1627. 1627         $carry = 0;
1628. 1628         $result = array();
1629. 1629 
1630. 1630         for ($i = count($dividend) - 1; $i >= 0; --$i) {
1631. 1631             $temp = MATH_BIGINTEGER_BASE_FULL * $carry + $dividend[$i];
1632. 1632             $result[$i] = $this->_safe_divide($temp, $divisor);
1633. 1633             $carry = (int) ($temp - $divisor * $result[$i]);
1634. 1634         }
1635. 1635 
1636. 1636         return array($result, $carry);
1637. 1637     }
1638. 1638 
1639. 1639     /**
1640. 1640      * Performs modular exponentiation.
1641. 1641      *
1642. 1642      * Here's an example:
1643. 1643      * <code>
1644. 1644      * <?php
1645. 1645      *    include 'Math/BigInteger.php';
1646. 1646      *
1647. 1647      *    $a = new Math_BigInteger('10');
1648. 1648      *    $b = new Math_BigInteger('20');
1649. 1649      *    $c = new Math_BigInteger('30');
1650. 1650      *
1651. 1651      *    $c = $a->modPow($b, $c);
1652. 1652      *
1653. 1653      *    echo $c->toString(); // outputs 10
1654. 1654      * ?>
1655. 1655      * </code>
1656. 1656      *
1657. 1657      * @param Math_BigInteger $e
1658. 1658      * @param Math_BigInteger $n
1659. 1659      * @return Math_BigInteger
1660. 1660      * @access public
1661. 1661      * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
1662. 1662      *    and although the approach involving repeated squaring does vastly better, it, too, is impractical
1663. 1663      *    for our purposes.  The reason being that division - by far the most complicated and time-consuming
1664. 1664      *    of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
1665. 1665      *
1666. 1666      *    Modular reductions resolve this issue.  Although an individual modular reduction takes more time
1667. 1667      *    then an individual division, when performed in succession (with the same modulo), they're a lot faster.
1668. 1668      *
1669. 1669      *    The two most commonly used modular reductions are Barrett and Montgomery reduction.  Montgomery reduction,
1670. 1670      *    although faster, only works when the gcd of the modulo and of the base being used is 1.  In RSA, when the
1671. 1671      *    base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
1672. 1672      *    the product of two odd numbers is odd), but what about when RSA isn't used?
1673. 1673      *
1674. 1674      *    In contrast, Barrett reduction has no such constraint.  As such, some bigint implementations perform a
1675. 1675      *    Barrett reduction after every operation in the modpow function.  Others perform Barrett reductions when the
1676. 1676      *    modulo is even and Montgomery reductions when the modulo is odd.  BigInteger.java's modPow method, however,
1677. 1677      *    uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
1678. 1678      *    the other, a power of two - and recombine them, later.  This is the method that this modPow function uses.
1679. 1679      *    {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
1680. 1680      */
1681. 1681     function modPow($e, $n)
1682. 1682     {
1683. 1683         $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
1684. 1684 
1685. 1685         if ($e->compare(new Math_BigInteger()) < 0) {
1686. 1686             $e = $e->abs();
1687. 1687 
1688. 1688             $temp = $this->modInverse($n);
1689. 1689             if ($temp === false) {
1690. 1690                 return false;
1691. 1691             }
1692. 1692 
1693. 1693             return $this->_normalize($temp->modPow($e, $n));
1694. 1694         }
1695. 1695 
1696. 1696         if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP) {
1697. 1697             $temp = new Math_BigInteger();
1698. 1698             $temp->value = gmp_powm($this->value, $e->value, $n->value);
1699. 1699 
1700. 1700             return $this->_normalize($temp);
1701. 1701         }
1702. 1702 
1703. 1703         if ($this->compare(new Math_BigInteger()) < 0 || $this->compare($n) > 0) {
1704. 1704             list(, $temp) = $this->divide($n);
1705. 1705             return $temp->modPow($e, $n);
1706. 1706         }
1707. 1707 
1708. 1708         if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
1709. 1709             $components = array(
1710. 1710                 'modulus' => $n->toBytes(true),
1711. 1711                 'publicExponent' => $e->toBytes(true)
1712. 1712             );
1713. 1713 
1714. 1714             $components = array(
1715. 1715                 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
1716. 1716                 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
1717. 1717             );
1718. 1718 
1719. 1719             $RSAPublicKey = pack(
1720. 1720                 'Ca*a*a*',
1721. 1721                 48,
1722. 1722                 $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
1723. 1723                 $components['modulus'],
1724. 1724                 $components['publicExponent']
1725. 1725             );
1726. 1726 
1727. 1727             $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
1728. 1728             $RSAPublicKey = chr(0) . $RSAPublicKey;
1729. 1729             $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
1730. 1730 
1731. 1731             $encapsulated = pack(
1732. 1732                 'Ca*a*',
1733. 1733                 48,
1734. 1734                 $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)),
1735. 1735                 $rsaOID . $RSAPublicKey
1736. 1736             );
1737. 1737 
1738. 1738             $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
1739. 1739                              chunk_split(base64_encode($encapsulated)) .
1740. 1740                              '-----END PUBLIC KEY-----';
1741. 1741 
1742. 1742             $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
1743. 1743 
1744. 1744             if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
1745. 1745                 return new Math_BigInteger($result, 256);
1746. 1746             }
1747. 1747         }
1748. 1748 
1749. 1749         if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
1750. 1750             $temp = new Math_BigInteger();
1751. 1751             $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
1752. 1752 
1753. 1753             return $this->_normalize($temp);
1754. 1754         }
1755. 1755 
1756. 1756         if (empty($e->value)) {
1757. 1757             $temp = new Math_BigInteger();
1758. 1758             $temp->value = array(1);
1759. 1759             return $this->_normalize($temp);
1760. 1760         }
1761. 1761 
1762. 1762         if ($e->value == array(1)) {
1763. 1763             list(, $temp) = $this->divide($n);
1764. 1764             return $this->_normalize($temp);
1765. 1765         }
1766. 1766 
1767. 1767         if ($e->value == array(2)) {
1768. 1768             $temp = new Math_BigInteger();
1769. 1769             $temp->value = $this->_square($this->value);
1770. 1770             list(, $temp) = $temp->divide($n);
1771. 1771             return $this->_normalize($temp);
1772. 1772         }
1773. 1773 
1774. 1774         return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT));
1775. 1775 
1776. 1776         // the following code, although not callable, can be run independently of the above code
1777. 1777         // although the above code performed better in my benchmarks the following could might
1778. 1778         // perform better under different circumstances. in lieu of deleting it it's just been
1779. 1779         // made uncallable
1780. 1780 
1781. 1781         // is the modulo odd?
1782. 1782         if ($n->value[0] & 1) {
1783. 1783             return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY));
1784. 1784         }
1785. 1785         // if it's not, it's even
1786. 1786 
1787. 1787         // find the lowest set bit (eg. the max pow of 2 that divides $n)
1788. 1788         for ($i = 0; $i < count($n->value); ++$i) {
1789. 1789             if ($n->value[$i]) {
1790. 1790                 $temp = decbin($n->value[$i]);
1791. 1791                 $j = strlen($temp) - strrpos($temp, '1') - 1;
1792. 1792                 $j+= 26 * $i;
1793. 1793                 break;
1794. 1794             }
1795. 1795         }
1796. 1796         // at this point, 2^$j * $n/(2^$j) == $n
1797. 1797 
1798. 1798         $mod1 = $n->copy();
1799. 1799         $mod1->_rshift($j);
1800. 1800         $mod2 = new Math_BigInteger();
1801. 1801         $mod2->value = array(1);
1802. 1802         $mod2->_lshift($j);
1803. 1803 
1804. 1804         $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger();
1805. 1805         $part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2);
1806. 1806 
1807. 1807         $y1 = $mod2->modInverse($mod1);
1808. 1808         $y2 = $mod1->modInverse($mod2);
1809. 1809 
1810. 1810         $result = $part1->multiply($mod2);
1811. 1811         $result = $result->multiply($y1);
1812. 1812 
1813. 1813         $temp = $part2->multiply($mod1);
1814. 1814         $temp = $temp->multiply($y2);
1815. 1815 
1816. 1816         $result = $result->add($temp);
1817. 1817         list(, $result) = $result->divide($n);
1818. 1818 
1819. 1819         return $this->_normalize($result);
1820. 1820     }
1821. 1821 
1822. 1822     /**
1823. 1823      * Performs modular exponentiation.
1824. 1824      *
1825. 1825      * Alias for Math_BigInteger::modPow()
1826. 1826      *
1827. 1827      * @param Math_BigInteger $e
1828. 1828      * @param Math_BigInteger $n
1829. 1829      * @return Math_BigInteger
1830. 1830      * @access public
1831. 1831      */
1832. 1832     function powMod($e, $n)
1833. 1833     {
1834. 1834         return $this->modPow($e, $n);
1835. 1835     }
1836. 1836 
1837. 1837     /**
1838. 1838      * Sliding Window k-ary Modular Exponentiation
1839. 1839      *
1840. 1840      * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
1841. 1841      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}.  In a departure from those algorithims,
1842. 1842      * however, this function performs a modular reduction after every multiplication and squaring operation.
1843. 1843      * As such, this function has the same preconditions that the reductions being used do.
1844. 1844      *
1845. 1845      * @param Math_BigInteger $e
1846. 1846      * @param Math_BigInteger $n
1847. 1847      * @param int $mode
1848. 1848      * @return Math_BigInteger
1849. 1849      * @access private
1850. 1850      */
1851. 1851     function _slidingWindow($e, $n, $mode)
1852. 1852     {
1853. 1853         static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
1854. 1854         //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
1855. 1855 
1856. 1856         $e_value = $e->value;
1857. 1857         $e_length = count($e_value) - 1;
1858. 1858         $e_bits = decbin($e_value[$e_length]);
1859. 1859         for ($i = $e_length - 1; $i >= 0; --$i) {
1860. 1860             $e_bits.= str_pad(decbin($e_value[$i]), MATH_BIGINTEGER_BASE, '0', STR_PAD_LEFT);
1861. 1861         }
1862. 1862 
1863. 1863         $e_length = strlen($e_bits);
1864. 1864 
1865. 1865         // calculate the appropriate window size.
1866. 1866         // $window_size == 3 if $window_ranges is between 25 and 81, for example.
1867. 1867         for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) {
1868. 1868         }
1869. 1869 
1870. 1870         $n_value = $n->value;
1871. 1871 
1872. 1872         // precompute $this^0 through $this^$window_size
1873. 1873         $powers = array();
1874. 1874         $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
1875. 1875         $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
1876. 1876 
1877. 1877         // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
1878. 1878         // in a 1.  ie. it's supposed to be odd.
1879. 1879         $temp = 1 << ($window_size - 1);
1880. 1880         for ($i = 1; $i < $temp; ++$i) {
1881. 1881             $i2 = $i << 1;
1882. 1882             $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
1883. 1883         }
1884. 1884 
1885. 1885         $result = array(1);
1886. 1886         $result = $this->_prepareReduce($result, $n_value, $mode);
1887. 1887 
1888. 1888         for ($i = 0; $i < $e_length;) {
1889. 1889             if (!$e_bits[$i]) {
1890. 1890                 $result = $this->_squareReduce($result, $n_value, $mode);
1891. 1891                 ++$i;
1892. 1892             } else {
1893. 1893                 for ($j = $window_size - 1; $j > 0; --$j) {
1894. 1894                     if (!empty($e_bits[$i + $j])) {
1895. 1895                         break;
1896. 1896                     }
1897. 1897                 }
1898. 1898 
1899. 1899                 // eg. the length of substr($e_bits, $i, $j + 1)
1900. 1900                 for ($k = 0; $k <= $j; ++$k) {
1901. 1901                     $result = $this->_squareReduce($result, $n_value, $mode);
1902. 1902                 }
1903. 1903 
1904. 1904                 $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
1905. 1905 
1906. 1906                 $i += $j + 1;
1907. 1907             }
1908. 1908         }
1909. 1909 
1910. 1910         $temp = new Math_BigInteger();
1911. 1911         $temp->value = $this->_reduce($result, $n_value, $mode);
1912. 1912 
1913. 1913         return $temp;
1914. 1914     }
1915. 1915 
1916. 1916     /**
1917. 1917      * Modular reduction
1918. 1918      *
1919. 1919      * For most $modes this will return the remainder.
1920. 1920      *
1921. 1921      * @see self::_slidingWindow()
1922. 1922      * @access private
1923. 1923      * @param array $x
1924. 1924      * @param array $n
1925. 1925      * @param int $mode
1926. 1926      * @return array
1927. 1927      */
1928. 1928     function _reduce($x, $n, $mode)
1929. 1929     {
1930. 1930         switch ($mode) {
1931. 1931             case MATH_BIGINTEGER_MONTGOMERY:
1932. 1932                 return $this->_montgomery($x, $n);
1933. 1933             case MATH_BIGINTEGER_BARRETT:
1934. 1934                 return $this->_barrett($x, $n);
1935. 1935             case MATH_BIGINTEGER_POWEROF2:
1936. 1936                 $lhs = new Math_BigInteger();
1937. 1937                 $lhs->value = $x;
1938. 1938                 $rhs = new Math_BigInteger();
1939. 1939                 $rhs->value = $n;
1940. 1940                 return $x->_mod2($n);
1941. 1941             case MATH_BIGINTEGER_CLASSIC:
1942. 1942                 $lhs = new Math_BigInteger();
1943. 1943                 $lhs->value = $x;
1944. 1944                 $rhs = new Math_BigInteger();
1945. 1945                 $rhs->value = $n;
1946. 1946                 list(, $temp) = $lhs->divide($rhs);
1947. 1947                 return $temp->value;
1948. 1948             case MATH_BIGINTEGER_NONE:
1949. 1949                 return $x;
1950. 1950             default:
1951. 1951                 // an invalid $mode was provided
1952. 1952         }
1953. 1953     }
1954. 1954 
1955. 1955     /**
1956. 1956      * Modular reduction preperation
1957. 1957      *
1958. 1958      * @see self::_slidingWindow()
1959. 1959      * @access private
1960. 1960      * @param array $x
1961. 1961      * @param array $n
1962. 1962      * @param int $mode
1963. 1963      * @return array
1964. 1964      */
1965. 1965     function _prepareReduce($x, $n, $mode)
1966. 1966     {
1967. 1967         if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
1968. 1968             return $this->_prepMontgomery($x, $n);
1969. 1969         }
1970. 1970         return $this->_reduce($x, $n, $mode);
1971. 1971     }
1972. 1972 
1973. 1973     /**
1974. 1974      * Modular multiply
1975. 1975      *
1976. 1976      * @see self::_slidingWindow()
1977. 1977      * @access private
1978. 1978      * @param array $x
1979. 1979      * @param array $y
1980. 1980      * @param array $n
1981. 1981      * @param int $mode
1982. 1982      * @return array
1983. 1983      */
1984. 1984     function _multiplyReduce($x, $y, $n, $mode)
1985. 1985     {
1986. 1986         if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
1987. 1987             return $this->_montgomeryMultiply($x, $y, $n);
1988. 1988         }
1989. 1989         $temp = $this->_multiply($x, false, $y, false);
1990. 1990         return $this->_reduce($temp[MATH_BIGINTEGER_VALUE], $n, $mode);
1991. 1991     }
1992. 1992 
1993. 1993     /**
1994. 1994      * Modular square
1995. 1995      *
1996. 1996      * @see self::_slidingWindow()
1997. 1997      * @access private
1998. 1998      * @param array $x
1999. 1999      * @param array $n
2000. 2000      * @param int $mode
2001. 2001      * @return array
2002. 2002      */
2003. 2003     function _squareReduce($x, $n, $mode)
2004. 2004     {
2005. 2005         if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
2006. 2006             return $this->_montgomeryMultiply($x, $x, $n);
2007. 2007         }
2008. 2008         return $this->_reduce($this->_square($x), $n, $mode);
2009. 2009     }
2010. 2010 
2011. 2011     /**
2012. 2012      * Modulos for Powers of Two
2013. 2013      *
2014. 2014      * Calculates $x%$n, where $n = 2**$e, for some $e.  Since this is basically the same as doing $x & ($n-1),
2015. 2015      * we'll just use this function as a wrapper for doing that.
2016. 2016      *
2017. 2017      * @see self::_slidingWindow()
2018. 2018      * @access private
2019. 2019      * @param Math_BigInteger
2020. 2020      * @return Math_BigInteger
2021. 2021      */
2022. 2022     function _mod2($n)
2023. 2023     {
2024. 2024         $temp = new Math_BigInteger();
2025. 2025         $temp->value = array(1);
2026. 2026         return $this->bitwise_and($n->subtract($temp));
2027. 2027     }
2028. 2028 
2029. 2029     /**
2030. 2030      * Barrett Modular Reduction
2031. 2031      *
2032. 2032      * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
2033. 2033      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
2034. 2034      * so as not to require negative numbers (initially, this script didn't support negative numbers).
2035. 2035      *
2036. 2036      * Employs "folding", as described at
2037. 2037      * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
2038. 2038      * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."
2039. 2039      *
2040. 2040      * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
2041. 2041      * usable on account of (1) its not using reasonable radix points as discussed in
2042. 2042      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
2043. 2043      * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
2044. 2044      * (x >> 1) + (x >> 1) != x / 2 + x / 2.  If x is even, they're the same, but if x is odd, they're not.  See the in-line
2045. 2045      * comments for details.
2046. 2046      *
2047. 2047      * @see self::_slidingWindow()
2048. 2048      * @access private
2049. 2049      * @param array $n
2050. 2050      * @param array $m
2051. 2051      * @return array
2052. 2052      */
2053. 2053     function _barrett($n, $m)
2054. 2054     {
2055. 2055         static $cache = array(
2056. 2056             MATH_BIGINTEGER_VARIABLE => array(),
2057. 2057             MATH_BIGINTEGER_DATA => array()
2058. 2058         );
2059. 2059 
2060. 2060         $m_length = count($m);
2061. 2061 
2062. 2062         // if ($this->_compare($n, $this->_square($m)) >= 0) {
2063. 2063         if (count($n) > 2 * $m_length) {
2064. 2064             $lhs = new Math_BigInteger();
2065. 2065             $rhs = new Math_BigInteger();
2066. 2066             $lhs->value = $n;
2067. 2067             $rhs->value = $m;
2068. 2068             list(, $temp) = $lhs->divide($rhs);
2069. 2069             return $temp->value;
2070. 2070         }
2071. 2071 
2072. 2072         // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
2073. 2073         if ($m_length < 5) {
2074. 2074             return $this->_regularBarrett($n, $m);
2075. 2075         }
2076. 2076 
2077. 2077         // n = 2 * m.length
2078. 2078 
2079. 2079         if (($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false) {
2080. 2080             $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
2081. 2081             $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
2082. 2082 
2083. 2083             $lhs = new Math_BigInteger();
2084. 2084             $lhs_value = &$lhs->value;
2085. 2085             $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
2086. 2086             $lhs_value[] = 1;
2087. 2087             $rhs = new Math_BigInteger();
2088. 2088             $rhs->value = $m;
2089. 2089 
2090. 2090             list($u, $m1) = $lhs->divide($rhs);
2091. 2091             $u = $u->value;
2092. 2092             $m1 = $m1->value;
2093. 2093 
2094. 2094             $cache[MATH_BIGINTEGER_DATA][] = array(
2095. 2095                 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
2096. 2096                 'm1'=> $m1 // m.length
2097. 2097             );
2098. 2098         } else {
2099. 2099             extract($cache[MATH_BIGINTEGER_DATA][$key]);
2100. 2100         }
2101. 2101 
2102. 2102         $cutoff = $m_length + ($m_length >> 1);
2103. 2103         $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
2104. 2104         $msd = array_slice($n, $cutoff);    // m.length >> 1
2105. 2105         $lsd = $this->_trim($lsd);
2106. 2106         $temp = $this->_multiply($msd, false, $m1, false);
2107. 2107         $n = $this->_add($lsd, false, $temp[MATH_BIGINTEGER_VALUE], false); // m.length + (m.length >> 1) + 1
2108. 2108 
2109. 2109         if ($m_length & 1) {
2110. 2110             return $this->_regularBarrett($n[MATH_BIGINTEGER_VALUE], $m);
2111. 2111         }
2112. 2112 
2113. 2113         // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
2114. 2114         $temp = array_slice($n[MATH_BIGINTEGER_VALUE], $m_length - 1);
2115. 2115         // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
2116. 2116         // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
2117. 2117         $temp = $this->_multiply($temp, false, $u, false);
2118. 2118         // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
2119. 2119         // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
2120. 2120         $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], ($m_length >> 1) + 1);
2121. 2121         // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
2122. 2122         // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
2123. 2123         $temp = $this->_multiply($temp, false, $m, false);
2124. 2124 
2125. 2125         // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
2126. 2126         // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
2127. 2127         // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
2128. 2128 
2129. 2129         $result = $this->_subtract($n[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
2130. 2130 
2131. 2131         while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false) >= 0) {
2132. 2132             $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false);
2133. 2133         }
2134. 2134 
2135. 2135         return $result[MATH_BIGINTEGER_VALUE];
2136. 2136     }
2137. 2137 
2138. 2138     /**
2139. 2139      * (Regular) Barrett Modular Reduction
2140. 2140      *
2141. 2141      * For numbers with more than four digits Math_BigInteger::_barrett() is faster.  The difference between that and this
2142. 2142      * is that this function does not fold the denominator into a smaller form.
2143. 2143      *
2144. 2144      * @see self::_slidingWindow()
2145. 2145      * @access private
2146. 2146      * @param array $x
2147. 2147      * @param array $n
2148. 2148      * @return array
2149. 2149      */
2150. 2150     function _regularBarrett($x, $n)
2151. 2151     {
2152. 2152         static $cache = array(
2153. 2153             MATH_BIGINTEGER_VARIABLE => array(),
2154. 2154             MATH_BIGINTEGER_DATA => array()
2155. 2155         );
2156. 2156 
2157. 2157         $n_length = count($n);
2158. 2158 
2159. 2159         if (count($x) > 2 * $n_length) {
2160. 2160             $lhs = new Math_BigInteger();
2161. 2161             $rhs = new Math_BigInteger();
2162. 2162             $lhs->value = $x;
2163. 2163             $rhs->value = $n;
2164. 2164             list(, $temp) = $lhs->divide($rhs);
2165. 2165             return $temp->value;
2166. 2166         }
2167. 2167 
2168. 2168         if (($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false) {
2169. 2169             $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
2170. 2170             $cache[MATH_BIGINTEGER_VARIABLE][] = $n;
2171. 2171             $lhs = new Math_BigInteger();
2172. 2172             $lhs_value = &$lhs->value;
2173. 2173             $lhs_value = $this->_array_repeat(0, 2 * $n_length);
2174. 2174             $lhs_value[] = 1;
2175. 2175             $rhs = new Math_BigInteger();
2176. 2176             $rhs->value = $n;
2177. 2177             list($temp, ) = $lhs->divide($rhs); // m.length
2178. 2178             $cache[MATH_BIGINTEGER_DATA][] = $temp->value;
2179. 2179         }
2180. 2180 
2181. 2181         // 2 * m.length - (m.length - 1) = m.length + 1
2182. 2182         $temp = array_slice($x, $n_length - 1);
2183. 2183         // (m.length + 1) + m.length = 2 * m.length + 1
2184. 2184         $temp = $this->_multiply($temp, false, $cache[MATH_BIGINTEGER_DATA][$key], false);
2185. 2185         // (2 * m.length + 1) - (m.length - 1) = m.length + 2
2186. 2186         $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], $n_length + 1);
2187. 2187 
2188. 2188         // m.length + 1
2189. 2189         $result = array_slice($x, 0, $n_length + 1);
2190. 2190         // m.length + 1
2191. 2191         $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
2192. 2192         // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
2193. 2193 
2194. 2194         if ($this->_compare($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]) < 0) {
2195. 2195             $corrector_value = $this->_array_repeat(0, $n_length + 1);
2196. 2196             $corrector_value[count($corrector_value)] = 1;
2197. 2197             $result = $this->_add($result, false, $corrector_value, false);
2198. 2198             $result = $result[MATH_BIGINTEGER_VALUE];
2199. 2199         }
2200. 2200 
2201. 2201         // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
2202. 2202         $result = $this->_subtract($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]);
2203. 2203         while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false) > 0) {
2204. 2204             $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false);
2205. 2205         }
2206. 2206 
2207. 2207         return $result[MATH_BIGINTEGER_VALUE];
2208. 2208     }
2209. 2209 
2210. 2210     /**
2211. 2211      * Performs long multiplication up to $stop digits
2212. 2212      *
2213. 2213      * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
2214. 2214      *
2215. 2215      * @see self::_regularBarrett()
2216. 2216      * @param array $x_value
2217. 2217      * @param bool $x_negative
2218. 2218      * @param array $y_value
2219. 2219      * @param bool $y_negative
2220. 2220      * @param int $stop
2221. 2221      * @return array
2222. 2222      * @access private
2223. 2223      */
2224. 2224     function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
2225. 2225     {
2226. 2226         $x_length = count($x_value);
2227. 2227         $y_length = count($y_value);
2228. 2228 
2229. 2229         if (!$x_length || !$y_length) { // a 0 is being multiplied
2230. 2230             return array(
2231. 2231                 MATH_BIGINTEGER_VALUE => array(),
2232. 2232                 MATH_BIGINTEGER_SIGN => false
2233. 2233             );
2234. 2234         }
2235. 2235 
2236. 2236         if ($x_length < $y_length) {
2237. 2237             $temp = $x_value;
2238. 2238             $x_value = $y_value;
2239. 2239             $y_value = $temp;
2240. 2240 
2241. 2241             $x_length = count($x_value);
2242. 2242             $y_length = count($y_value);
2243. 2243         }
2244. 2244 
2245. 2245         $product_value = $this->_array_repeat(0, $x_length + $y_length);
2246. 2246 
2247. 2247         // the following for loop could be removed if the for loop following it
2248. 2248         // (the one with nested for loops) initially set $i to 0, but
2249. 2249         // doing so would also make the result in one set of unnecessary adds,
2250. 2250         // since on the outermost loops first pass, $product->value[$k] is going
2251. 2251         // to always be 0
2252. 2252 
2253. 2253         $carry = 0;
2254. 2254 
2255. 2255         for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
2256. 2256             $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
2257. 2257             $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2258. 2258             $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
2259. 2259         }
2260. 2260 
2261. 2261         if ($j < $stop) {
2262. 2262             $product_value[$j] = $carry;
2263. 2263         }
2264. 2264 
2265. 2265         // the above for loop is what the previous comment was talking about.  the
2266. 2266         // following for loop is the "one with nested for loops"
2267. 2267 
2268. 2268         for ($i = 1; $i < $y_length; ++$i) {
2269. 2269             $carry = 0;
2270. 2270 
2271. 2271             for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
2272. 2272                 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
2273. 2273                 $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2274. 2274                 $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
2275. 2275             }
2276. 2276 
2277. 2277             if ($k < $stop) {
2278. 2278                 $product_value[$k] = $carry;
2279. 2279             }
2280. 2280         }
2281. 2281 
2282. 2282         return array(
2283. 2283             MATH_BIGINTEGER_VALUE => $this->_trim($product_value),
2284. 2284             MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
2285. 2285         );
2286. 2286     }
2287. 2287 
2288. 2288     /**
2289. 2289      * Montgomery Modular Reduction
2290. 2290      *
2291. 2291      * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n.
2292. 2292      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be
2293. 2293      * improved upon (basically, by using the comba method).  gcd($n, 2) must be equal to one for this function
2294. 2294      * to work correctly.
2295. 2295      *
2296. 2296      * @see self::_prepMontgomery()
2297. 2297      * @see self::_slidingWindow()
2298. 2298      * @access private
2299. 2299      * @param array $x
2300. 2300      * @param array $n
2301. 2301      * @return array
2302. 2302      */
2303. 2303     function _montgomery($x, $n)
2304. 2304     {
2305. 2305         static $cache = array(
2306. 2306             MATH_BIGINTEGER_VARIABLE => array(),
2307. 2307             MATH_BIGINTEGER_DATA => array()
2308. 2308         );
2309. 2309 
2310. 2310         if (($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false) {
2311. 2311             $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
2312. 2312             $cache[MATH_BIGINTEGER_VARIABLE][] = $x;
2313. 2313             $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($n);
2314. 2314         }
2315. 2315 
2316. 2316         $k = count($n);
2317. 2317 
2318. 2318         $result = array(MATH_BIGINTEGER_VALUE => $x);
2319. 2319 
2320. 2320         for ($i = 0; $i < $k; ++$i) {
2321. 2321             $temp = $result[MATH_BIGINTEGER_VALUE][$i] * $cache[MATH_BIGINTEGER_DATA][$key];
2322. 2322             $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2323. 2323             $temp = $this->_regularMultiply(array($temp), $n);
2324. 2324             $temp = array_merge($this->_array_repeat(0, $i), $temp);
2325. 2325             $result = $this->_add($result[MATH_BIGINTEGER_VALUE], false, $temp, false);
2326. 2326         }
2327. 2327 
2328. 2328         $result[MATH_BIGINTEGER_VALUE] = array_slice($result[MATH_BIGINTEGER_VALUE], $k);
2329. 2329 
2330. 2330         if ($this->_compare($result, false, $n, false) >= 0) {
2331. 2331             $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], false, $n, false);
2332. 2332         }
2333. 2333 
2334. 2334         return $result[MATH_BIGINTEGER_VALUE];
2335. 2335     }
2336. 2336 
2337. 2337     /**
2338. 2338      * Montgomery Multiply
2339. 2339      *
2340. 2340      * Interleaves the montgomery reduction and long multiplication algorithms together as described in
2341. 2341      * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
2342. 2342      *
2343. 2343      * @see self::_prepMontgomery()
2344. 2344      * @see self::_montgomery()
2345. 2345      * @access private
2346. 2346      * @param array $x
2347. 2347      * @param array $y
2348. 2348      * @param array $m
2349. 2349      * @return array
2350. 2350      */
2351. 2351     function _montgomeryMultiply($x, $y, $m)
2352. 2352     {
2353. 2353         $temp = $this->_multiply($x, false, $y, false);
2354. 2354         return $this->_montgomery($temp[MATH_BIGINTEGER_VALUE], $m);
2355. 2355 
2356. 2356         // the following code, although not callable, can be run independently of the above code
2357. 2357         // although the above code performed better in my benchmarks the following could might
2358. 2358         // perform better under different circumstances. in lieu of deleting it it's just been
2359. 2359         // made uncallable
2360. 2360 
2361. 2361         static $cache = array(
2362. 2362             MATH_BIGINTEGER_VARIABLE => array(),
2363. 2363             MATH_BIGINTEGER_DATA => array()
2364. 2364         );
2365. 2365 
2366. 2366         if (($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false) {
2367. 2367             $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
2368. 2368             $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
2369. 2369             $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($m);
2370. 2370         }
2371. 2371 
2372. 2372         $n = max(count($x), count($y), count($m));
2373. 2373         $x = array_pad($x, $n, 0);
2374. 2374         $y = array_pad($y, $n, 0);
2375. 2375         $m = array_pad($m, $n, 0);
2376. 2376         $a = array(MATH_BIGINTEGER_VALUE => $this->_array_repeat(0, $n + 1));
2377. 2377         for ($i = 0; $i < $n; ++$i) {
2378. 2378             $temp = $a[MATH_BIGINTEGER_VALUE][0] + $x[$i] * $y[0];
2379. 2379             $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2380. 2380             $temp = $temp * $cache[MATH_BIGINTEGER_DATA][$key];
2381. 2381             $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2382. 2382             $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
2383. 2383             $a = $this->_add($a[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
2384. 2384             $a[MATH_BIGINTEGER_VALUE] = array_slice($a[MATH_BIGINTEGER_VALUE], 1);
2385. 2385         }
2386. 2386         if ($this->_compare($a[MATH_BIGINTEGER_VALUE], false, $m, false) >= 0) {
2387. 2387             $a = $this->_subtract($a[MATH_BIGINTEGER_VALUE], false, $m, false);
2388. 2388         }
2389. 2389         return $a[MATH_BIGINTEGER_VALUE];
2390. 2390     }
2391. 2391 
2392. 2392     /**
2393. 2393      * Prepare a number for use in Montgomery Modular Reductions
2394. 2394      *
2395. 2395      * @see self::_montgomery()
2396. 2396      * @see self::_slidingWindow()
2397. 2397      * @access private
2398. 2398      * @param array $x
2399. 2399      * @param array $n
2400. 2400      * @return array
2401. 2401      */
2402. 2402     function _prepMontgomery($x, $n)
2403. 2403     {
2404. 2404         $lhs = new Math_BigInteger();
2405. 2405         $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
2406. 2406         $rhs = new Math_BigInteger();
2407. 2407         $rhs->value = $n;
2408. 2408 
2409. 2409         list(, $temp) = $lhs->divide($rhs);
2410. 2410         return $temp->value;
2411. 2411     }
2412. 2412 
2413. 2413     /**
2414. 2414      * Modular Inverse of a number mod 2**26 (eg. 67108864)
2415. 2415      *
2416. 2416      * Based off of the bnpInvDigit function implemented and justified in the following URL:
2417. 2417      *
2418. 2418      * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
2419. 2419      *
2420. 2420      * The following URL provides more info:
2421. 2421      *
2422. 2422      * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
2423. 2423      *
2424. 2424      * As for why we do all the bitmasking...  strange things can happen when converting from floats to ints. For
2425. 2425      * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
2426. 2426      * int(-2147483648).  To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
2427. 2427      * auto-converted to floats.  The outermost bitmask is present because without it, there's no guarantee that
2428. 2428      * the "residue" returned would be the so-called "common residue".  We use fmod, in the last step, because the
2429. 2429      * maximum possible $x is 26 bits and the maximum $result is 16 bits.  Thus, we have to be able to handle up to
2430. 2430      * 40 bits, which only 64-bit floating points will support.
2431. 2431      *
2432. 2432      * Thanks to Pedro Gimeno Fortea for input!
2433. 2433      *
2434. 2434      * @see self::_montgomery()
2435. 2435      * @access private
2436. 2436      * @param array $x
2437. 2437      * @return int
2438. 2438      */
2439. 2439     function _modInverse67108864($x) // 2**26 == 67,108,864
2440. 2440     {
2441. 2441         $x = -$x[0];
2442. 2442         $result = $x & 0x3; // x**-1 mod 2**2
2443. 2443         $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
2444. 2444         $result = ($result * (2 - ($x & 0xFF) * $result))  & 0xFF; // x**-1 mod 2**8
2445. 2445         $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
2446. 2446         $result = fmod($result * (2 - fmod($x * $result, MATH_BIGINTEGER_BASE_FULL)), MATH_BIGINTEGER_BASE_FULL); // x**-1 mod 2**26
2447. 2447         return $result & MATH_BIGINTEGER_MAX_DIGIT;
2448. 2448     }
2449. 2449 
2450. 2450     /**
2451. 2451      * Calculates modular inverses.
2452. 2452      *
2453. 2453      * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
2454. 2454      *
2455. 2455      * Here's an example:
2456. 2456      * <code>
2457. 2457      * <?php
2458. 2458      *    include 'Math/BigInteger.php';
2459. 2459      *
2460. 2460      *    $a = new Math_BigInteger(30);
2461. 2461      *    $b = new Math_BigInteger(17);
2462. 2462      *
2463. 2463      *    $c = $a->modInverse($b);
2464. 2464      *    echo $c->toString(); // outputs 4
2465. 2465      *
2466. 2466      *    echo "\r\n";
2467. 2467      *
2468. 2468      *    $d = $a->multiply($c);
2469. 2469      *    list(, $d) = $d->divide($b);
2470. 2470      *    echo $d; // outputs 1 (as per the definition of modular inverse)
2471. 2471      * ?>
2472. 2472      * </code>
2473. 2473      *
2474. 2474      * @param Math_BigInteger $n
2475. 2475      * @return Math_BigInteger|false
2476. 2476      * @access public
2477. 2477      * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.
2478. 2478      */
2479. 2479     function modInverse($n)
2480. 2480     {
2481. 2481         switch (MATH_BIGINTEGER_MODE) {
2482. 2482             case MATH_BIGINTEGER_MODE_GMP:
2483. 2483                 $temp = new Math_BigInteger();
2484. 2484                 $temp->value = gmp_invert($this->value, $n->value);
2485. 2485 
2486. 2486                 return ($temp->value === false) ? false : $this->_normalize($temp);
2487. 2487         }
2488. 2488 
2489. 2489         static $zero, $one;
2490. 2490         if (!isset($zero)) {
2491. 2491             $zero = new Math_BigInteger();
2492. 2492             $one = new Math_BigInteger(1);
2493. 2493         }
2494. 2494 
2495. 2495         // $x mod -$n == $x mod $n.
2496. 2496         $n = $n->abs();
2497. 2497 
2498. 2498         if ($this->compare($zero) < 0) {
2499. 2499             $temp = $this->abs();
2500. 2500             $temp = $temp->modInverse($n);
2501. 2501             return $this->_normalize($n->subtract($temp));
2502. 2502         }
2503. 2503 
2504. 2504         extract($this->extendedGCD($n));
2505. 2505 
2506. 2506         if (!$gcd->equals($one)) {
2507. 2507             return false;
2508. 2508         }
2509. 2509 
2510. 2510         $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
2511. 2511 
2512. 2512         return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
2513. 2513     }
2514. 2514 
2515. 2515     /**
2516. 2516      * Calculates the greatest common divisor and Bezout's identity.
2517. 2517      *
2518. 2518      * Say you have 693 and 609.  The GCD is 21.  Bezout's identity states that there exist integers x and y such that
2519. 2519      * 693*x + 609*y == 21.  In point of fact, there are actually an infinite number of x and y combinations and which
2520. 2520      * combination is returned is dependent upon which mode is in use.  See
2521. 2521      * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
2522. 2522      *
2523. 2523      * Here's an example:
2524. 2524      * <code>
2525. 2525      * <?php
2526. 2526      *    include 'Math/BigInteger.php';
2527. 2527      *
2528. 2528      *    $a = new Math_BigInteger(693);
2529. 2529      *    $b = new Math_BigInteger(609);
2530. 2530      *
2531. 2531      *    extract($a->extendedGCD($b));
2532. 2532      *
2533. 2533      *    echo $gcd->toString() . "\r\n"; // outputs 21
2534. 2534      *    echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
2535. 2535      * ?>
2536. 2536      * </code>
2537. 2537      *
2538. 2538      * @param Math_BigInteger $n
2539. 2539      * @return Math_BigInteger
2540. 2540      * @access public
2541. 2541      * @internal Calculates the GCD using the binary xGCD algorithim described in
2542. 2542      *    {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}.  As the text above 14.61 notes,
2543. 2543      *    the more traditional algorithim requires "relatively costly multiple-precision divisions".
2544. 2544      */
2545. 2545     function extendedGCD($n)
2546. 2546     {
2547. 2547         switch (MATH_BIGINTEGER_MODE) {
2548. 2548             case MATH_BIGINTEGER_MODE_GMP:
2549. 2549                 extract(gmp_gcdext($this->value, $n->value));
2550. 2550 
2551. 2551                 return array(
2552. 2552                     'gcd' => $this->_normalize(new Math_BigInteger($g)),
2553. 2553                     'x'   => $this->_normalize(new Math_BigInteger($s)),
2554. 2554                     'y'   => $this->_normalize(new Math_BigInteger($t))
2555. 2555                 );
2556. 2556             case MATH_BIGINTEGER_MODE_BCMATH:
2557. 2557                 // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
2558. 2558                 // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway.  as is,
2559. 2559                 // the basic extended euclidean algorithim is what we're using.
2560. 2560 
2561. 2561                 $u = $this->value;
2562. 2562                 $v = $n->value;
2563. 2563 
2564. 2564                 $a = '1';
2565. 2565                 $b = '0';
2566. 2566                 $c = '0';
2567. 2567                 $d = '1';
2568. 2568 
2569. 2569                 while (bccomp($v, '0', 0) != 0) {
2570. 2570                     $q = bcdiv($u, $v, 0);
2571. 2571 
2572. 2572                     $temp = $u;
2573. 2573                     $u = $v;
2574. 2574                     $v = bcsub($temp, bcmul($v, $q, 0), 0);
2575. 2575 
2576. 2576                     $temp = $a;
2577. 2577                     $a = $c;
2578. 2578                     $c = bcsub($temp, bcmul($a, $q, 0), 0);
2579. 2579 
2580. 2580                     $temp = $b;
2581. 2581                     $b = $d;
2582. 2582                     $d = bcsub($temp, bcmul($b, $q, 0), 0);
2583. 2583                 }
2584. 2584 
2585. 2585                 return array(
2586. 2586                     'gcd' => $this->_normalize(new Math_BigInteger($u)),
2587. 2587                     'x'   => $this->_normalize(new Math_BigInteger($a)),
2588. 2588                     'y'   => $this->_normalize(new Math_BigInteger($b))
2589. 2589                 );
2590. 2590         }
2591. 2591 
2592. 2592         $y = $n->copy();
2593. 2593         $x = $this->copy();
2594. 2594         $g = new Math_BigInteger();
2595. 2595         $g->value = array(1);
2596. 2596 
2597. 2597         while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) {
2598. 2598             $x->_rshift(1);
2599. 2599             $y->_rshift(1);
2600. 2600             $g->_lshift(1);
2601. 2601         }
2602. 2602 
2603. 2603         $u = $x->copy();
2604. 2604         $v = $y->copy();
2605. 2605 
2606. 2606         $a = new Math_BigInteger();
2607. 2607         $b = new Math_BigInteger();
2608. 2608         $c = new Math_BigInteger();
2609. 2609         $d = new Math_BigInteger();
2610. 2610 
2611. 2611         $a->value = $d->value = $g->value = array(1);
2612. 2612         $b->value = $c->value = array();
2613. 2613 
2614. 2614         while (!empty($u->value)) {
2615. 2615             while (!($u->value[0] & 1)) {
2616. 2616                 $u->_rshift(1);
2617. 2617                 if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
2618. 2618                     $a = $a->add($y);
2619. 2619                     $b = $b->subtract($x);
2620. 2620                 }
2621. 2621                 $a->_rshift(1);
2622. 2622                 $b->_rshift(1);
2623. 2623             }
2624. 2624 
2625. 2625             while (!($v->value[0] & 1)) {
2626. 2626                 $v->_rshift(1);
2627. 2627                 if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) {
2628. 2628                     $c = $c->add($y);
2629. 2629                     $d = $d->subtract($x);
2630. 2630                 }
2631. 2631                 $c->_rshift(1);
2632. 2632                 $d->_rshift(1);
2633. 2633             }
2634. 2634 
2635. 2635             if ($u->compare($v) >= 0) {
2636. 2636                 $u = $u->subtract($v);
2637. 2637                 $a = $a->subtract($c);
2638. 2638                 $b = $b->subtract($d);
2639. 2639             } else {
2640. 2640                 $v = $v->subtract($u);
2641. 2641                 $c = $c->subtract($a);
2642. 2642                 $d = $d->subtract($b);
2643. 2643             }
2644. 2644         }
2645. 2645 
2646. 2646         return array(
2647. 2647             'gcd' => $this->_normalize($g->multiply($v)),
2648. 2648             'x'   => $this->_normalize($c),
2649. 2649             'y'   => $this->_normalize($d)
2650. 2650         );
2651. 2651     }
2652. 2652 
2653. 2653     /**
2654. 2654      * Calculates the greatest common divisor
2655. 2655      *
2656. 2656      * Say you have 693 and 609.  The GCD is 21.
2657. 2657      *
2658. 2658      * Here's an example:
2659. 2659      * <code>
2660. 2660      * <?php
2661. 2661      *    include 'Math/BigInteger.php';
2662. 2662      *
2663. 2663      *    $a = new Math_BigInteger(693);
2664. 2664      *    $b = new Math_BigInteger(609);
2665. 2665      *
2666. 2666      *    $gcd = a->extendedGCD($b);
2667. 2667      *
2668. 2668      *    echo $gcd->toString() . "\r\n"; // outputs 21
2669. 2669      * ?>
2670. 2670      * </code>
2671. 2671      *
2672. 2672      * @param Math_BigInteger $n
2673. 2673      * @return Math_BigInteger
2674. 2674      * @access public
2675. 2675      */
2676. 2676     function gcd($n)
2677. 2677     {
2678. 2678         extract($this->extendedGCD($n));
2679. 2679         return $gcd;
2680. 2680     }
2681. 2681 
2682. 2682     /**
2683. 2683      * Absolute value.
2684. 2684      *
2685. 2685      * @return Math_BigInteger
2686. 2686      * @access public
2687. 2687      */
2688. 2688     function abs()
2689. 2689     {
2690. 2690         $temp = new Math_BigInteger();
2691. 2691 
2692. 2692         switch (MATH_BIGINTEGER_MODE) {
2693. 2693             case MATH_BIGINTEGER_MODE_GMP:
2694. 2694                 $temp->value = gmp_abs($this->value);
2695. 2695                 break;
2696. 2696             case MATH_BIGINTEGER_MODE_BCMATH:
2697. 2697                 $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
2698. 2698                 break;
2699. 2699             default:
2700. 2700                 $temp->value = $this->value;
2701. 2701         }
2702. 2702 
2703. 2703         return $temp;
2704. 2704     }
2705. 2705 
2706. 2706     /**
2707. 2707      * Compares two numbers.
2708. 2708      *
2709. 2709      * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this is
2710. 2710      * demonstrated thusly:
2711. 2711      *
2712. 2712      * $x  > $y: $x->compare($y)  > 0
2713. 2713      * $x  < $y: $x->compare($y)  < 0
2714. 2714      * $x == $y: $x->compare($y) == 0
2715. 2715      *
2716. 2716      * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
2717. 2717      *
2718. 2718      * @param Math_BigInteger $y
2719. 2719      * @return int < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
2720. 2720      * @access public
2721. 2721      * @see self::equals()
2722. 2722      * @internal Could return $this->subtract($x), but that's not as fast as what we do do.
2723. 2723      */
2724. 2724     function compare($y)
2725. 2725     {
2726. 2726         switch (MATH_BIGINTEGER_MODE) {
2727. 2727             case MATH_BIGINTEGER_MODE_GMP:
2728. 2728                 return gmp_cmp($this->value, $y->value);
2729. 2729             case MATH_BIGINTEGER_MODE_BCMATH:
2730. 2730                 return bccomp($this->value, $y->value, 0);
2731. 2731         }
2732. 2732 
2733. 2733         return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
2734. 2734     }
2735. 2735 
2736. 2736     /**
2737. 2737      * Compares two numbers.
2738. 2738      *
2739. 2739      * @param array $x_value
2740. 2740      * @param bool $x_negative
2741. 2741      * @param array $y_value
2742. 2742      * @param bool $y_negative
2743. 2743      * @return int
2744. 2744      * @see self::compare()
2745. 2745      * @access private
2746. 2746      */
2747. 2747     function _compare($x_value, $x_negative, $y_value, $y_negative)
2748. 2748     {
2749. 2749         if ($x_negative != $y_negative) {
2750. 2750             return (!$x_negative && $y_negative) ? 1 : -1;
2751. 2751         }
2752. 2752 
2753. 2753         $result = $x_negative ? -1 : 1;
2754. 2754 
2755. 2755         if (count($x_value) != count($y_value)) {
2756. 2756             return (count($x_value) > count($y_value)) ? $result : -$result;
2757. 2757         }
2758. 2758         $size = max(count($x_value), count($y_value));
2759. 2759 
2760. 2760         $x_value = array_pad($x_value, $size, 0);
2761. 2761         $y_value = array_pad($y_value, $size, 0);
2762. 2762 
2763. 2763         for ($i = count($x_value) - 1; $i >= 0; --$i) {
2764. 2764             if ($x_value[$i] != $y_value[$i]) {
2765. 2765                 return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
2766. 2766             }
2767. 2767         }
2768. 2768 
2769. 2769         return 0;
2770. 2770     }
2771. 2771 
2772. 2772     /**
2773. 2773      * Tests the equality of two numbers.
2774. 2774      *
2775. 2775      * If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare()
2776. 2776      *
2777. 2777      * @param Math_BigInteger $x
2778. 2778      * @return bool
2779. 2779      * @access public
2780. 2780      * @see self::compare()
2781. 2781      */
2782. 2782     function equals($x)
2783. 2783     {
2784. 2784         switch (MATH_BIGINTEGER_MODE) {
2785. 2785             case MATH_BIGINTEGER_MODE_GMP:
2786. 2786                 return gmp_cmp($this->value, $x->value) == 0;
2787. 2787             default:
2788. 2788                 return $this->value === $x->value && $this->is_negative == $x->is_negative;
2789. 2789         }
2790. 2790     }
2791. 2791 
2792. 2792     /**
2793. 2793      * Set Precision
2794. 2794      *
2795. 2795      * Some bitwise operations give different results depending on the precision being used.  Examples include left
2796. 2796      * shift, not, and rotates.
2797. 2797      *
2798. 2798      * @param int $bits
2799. 2799      * @access public
2800. 2800      */
2801. 2801     function setPrecision($bits)
2802. 2802     {
2803. 2803         $this->precision = $bits;
2804. 2804         if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH) {
2805. 2805             $this->bitmask = new Math_BigInteger(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
2806. 2806         } else {
2807. 2807             $this->bitmask = new Math_BigInteger(bcpow('2', $bits, 0));
2808. 2808         }
2809. 2809 
2810. 2810         $temp = $this->_normalize($this);
2811. 2811         $this->value = $temp->value;
2812. 2812     }
2813. 2813 
2814. 2814     /**
2815. 2815      * Logical And
2816. 2816      *
2817. 2817      * @param Math_BigInteger $x
2818. 2818      * @access public
2819. 2819      * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2820. 2820      * @return Math_BigInteger
2821. 2821      */
2822. 2822     function bitwise_and($x)
2823. 2823     {
2824. 2824         switch (MATH_BIGINTEGER_MODE) {
2825. 2825             case MATH_BIGINTEGER_MODE_GMP:
2826. 2826                 $temp = new Math_BigInteger();
2827. 2827                 $temp->value = gmp_and($this->value, $x->value);
2828. 2828 
2829. 2829                 return $this->_normalize($temp);
2830. 2830             case MATH_BIGINTEGER_MODE_BCMATH:
2831. 2831                 $left = $this->toBytes();
2832. 2832                 $right = $x->toBytes();
2833. 2833 
2834. 2834                 $length = max(strlen($left), strlen($right));
2835. 2835 
2836. 2836                 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2837. 2837                 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2838. 2838 
2839. 2839                 return $this->_normalize(new Math_BigInteger($left & $right, 256));
2840. 2840         }
2841. 2841 
2842. 2842         $result = $this->copy();
2843. 2843 
2844. 2844         $length = min(count($x->value), count($this->value));
2845. 2845 
2846. 2846         $result->value = array_slice($result->value, 0, $length);
2847. 2847 
2848. 2848         for ($i = 0; $i < $length; ++$i) {
2849. 2849             $result->value[$i]&= $x->value[$i];
2850. 2850         }
2851. 2851 
2852. 2852         return $this->_normalize($result);
2853. 2853     }
2854. 2854 
2855. 2855     /**
2856. 2856      * Logical Or
2857. 2857      *
2858. 2858      * @param Math_BigInteger $x
2859. 2859      * @access public
2860. 2860      * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2861. 2861      * @return Math_BigInteger
2862. 2862      */
2863. 2863     function bitwise_or($x)
2864. 2864     {
2865. 2865         switch (MATH_BIGINTEGER_MODE) {
2866. 2866             case MATH_BIGINTEGER_MODE_GMP:
2867. 2867                 $temp = new Math_BigInteger();
2868. 2868                 $temp->value = gmp_or($this->value, $x->value);
2869. 2869 
2870. 2870                 return $this->_normalize($temp);
2871. 2871             case MATH_BIGINTEGER_MODE_BCMATH:
2872. 2872                 $left = $this->toBytes();
2873. 2873                 $right = $x->toBytes();
2874. 2874 
2875. 2875                 $length = max(strlen($left), strlen($right));
2876. 2876 
2877. 2877                 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2878. 2878                 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2879. 2879 
2880. 2880                 return $this->_normalize(new Math_BigInteger($left | $right, 256));
2881. 2881         }
2882. 2882 
2883. 2883         $length = max(count($this->value), count($x->value));
2884. 2884         $result = $this->copy();
2885. 2885         $result->value = array_pad($result->value, $length, 0);
2886. 2886         $x->value = array_pad($x->value, $length, 0);
2887. 2887 
2888. 2888         for ($i = 0; $i < $length; ++$i) {
2889. 2889             $result->value[$i]|= $x->value[$i];
2890. 2890         }
2891. 2891 
2892. 2892         return $this->_normalize($result);
2893. 2893     }
2894. 2894 
2895. 2895     /**
2896. 2896      * Logical Exclusive-Or
2897. 2897      *
2898. 2898      * @param Math_BigInteger $x
2899. 2899      * @access public
2900. 2900      * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2901. 2901      * @return Math_BigInteger
2902. 2902      */
2903. 2903     function bitwise_xor($x)
2904. 2904     {
2905. 2905         switch (MATH_BIGINTEGER_MODE) {
2906. 2906             case MATH_BIGINTEGER_MODE_GMP:
2907. 2907                 $temp = new Math_BigInteger();
2908. 2908                 $temp->value = gmp_xor(gmp_abs($this->value), gmp_abs($x->value));
2909. 2909 
2910. 2910                 return $this->_normalize($temp);
2911. 2911             case MATH_BIGINTEGER_MODE_BCMATH:
2912. 2912                 $left = $this->toBytes();
2913. 2913                 $right = $x->toBytes();
2914. 2914 
2915. 2915                 $length = max(strlen($left), strlen($right));
2916. 2916 
2917. 2917                 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2918. 2918                 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2919. 2919 
2920. 2920                 return $this->_normalize(new Math_BigInteger($left ^ $right, 256));
2921. 2921         }
2922. 2922 
2923. 2923         $length = max(count($this->value), count($x->value));
2924. 2924         $result = $this->copy();
2925. 2925         $result->is_negative = false;
2926. 2926         $result->value = array_pad($result->value, $length, 0);
2927. 2927         $x->value = array_pad($x->value, $length, 0);
2928. 2928 
2929. 2929         for ($i = 0; $i < $length; ++$i) {
2930. 2930             $result->value[$i]^= $x->value[$i];
2931. 2931         }
2932. 2932 
2933. 2933         return $this->_normalize($result);
2934. 2934     }
2935. 2935 
2936. 2936     /**
2937. 2937      * Logical Not
2938. 2938      *
2939. 2939      * @access public
2940. 2940      * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2941. 2941      * @return Math_BigInteger
2942. 2942      */
2943. 2943     function bitwise_not()
2944. 2944     {
2945. 2945         // calculuate "not" without regard to $this->precision
2946. 2946         // (will always result in a smaller number.  ie. ~1 isn't 1111 1110 - it's 0)
2947. 2947         $temp = $this->toBytes();
2948. 2948         if ($temp == '') {
2949. 2949             return $this->_normalize(new Math_BigInteger());
2950. 2950         }
2951. 2951         $pre_msb = decbin(ord($temp[0]));
2952. 2952         $temp = ~$temp;
2953. 2953         $msb = decbin(ord($temp[0]));
2954. 2954         if (strlen($msb) == 8) {
2955. 2955             $msb = substr($msb, strpos($msb, '0'));
2956. 2956         }
2957. 2957         $temp[0] = chr(bindec($msb));
2958. 2958 
2959. 2959         // see if we need to add extra leading 1's
2960. 2960         $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
2961. 2961         $new_bits = $this->precision - $current_bits;
2962. 2962         if ($new_bits <= 0) {
2963. 2963             return $this->_normalize(new Math_BigInteger($temp, 256));
2964. 2964         }
2965. 2965 
2966. 2966         // generate as many leading 1's as we need to.
2967. 2967         $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
2968. 2968         $this->_base256_lshift($leading_ones, $current_bits);
2969. 2969 
2970. 2970         $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
2971. 2971 
2972. 2972         return $this->_normalize(new Math_BigInteger($leading_ones | $temp, 256));
2973. 2973     }
2974. 2974 
2975. 2975     /**
2976. 2976      * Logical Right Shift
2977. 2977      *
2978. 2978      * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
2979. 2979      *
2980. 2980      * @param int $shift
2981. 2981      * @return Math_BigInteger
2982. 2982      * @access public
2983. 2983      * @internal The only version that yields any speed increases is the internal version.
2984. 2984      */
2985. 2985     function bitwise_rightShift($shift)
2986. 2986     {
2987. 2987         $temp = new Math_BigInteger();
2988. 2988 
2989. 2989         switch (MATH_BIGINTEGER_MODE) {
2990. 2990             case MATH_BIGINTEGER_MODE_GMP:
2991. 2991                 static $two;
2992. 2992 
2993. 2993                 if (!isset($two)) {
2994. 2994                     $two = gmp_init('2');
2995. 2995                 }
2996. 2996 
2997. 2997                 $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
2998. 2998 
2999. 2999                 break;
3000. 3000             case MATH_BIGINTEGER_MODE_BCMATH:
3001. 3001                 $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
3002. 3002 
3003. 3003                 break;
3004. 3004             default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
3005. 3005                      // and I don't want to do that...
3006. 3006                 $temp->value = $this->value;
3007. 3007                 $temp->_rshift($shift);
3008. 3008         }
3009. 3009 
3010. 3010         return $this->_normalize($temp);
3011. 3011     }
3012. 3012 
3013. 3013     /**
3014. 3014      * Logical Left Shift
3015. 3015      *
3016. 3016      * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
3017. 3017      *
3018. 3018      * @param int $shift
3019. 3019      * @return Math_BigInteger
3020. 3020      * @access public
3021. 3021      * @internal The only version that yields any speed increases is the internal version.
3022. 3022      */
3023. 3023     function bitwise_leftShift($shift)
3024. 3024     {
3025. 3025         $temp = new Math_BigInteger();
3026. 3026 
3027. 3027         switch (MATH_BIGINTEGER_MODE) {
3028. 3028             case MATH_BIGINTEGER_MODE_GMP:
3029. 3029                 static $two;
3030. 3030 
3031. 3031                 if (!isset($two)) {
3032. 3032                     $two = gmp_init('2');
3033. 3033                 }
3034. 3034 
3035. 3035                 $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
3036. 3036 
3037. 3037                 break;
3038. 3038             case MATH_BIGINTEGER_MODE_BCMATH:
3039. 3039                 $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
3040. 3040 
3041. 3041                 break;
3042. 3042             default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
3043. 3043                      // and I don't want to do that...
3044. 3044                 $temp->value = $this->value;
3045. 3045                 $temp->_lshift($shift);
3046. 3046         }
3047. 3047 
3048. 3048         return $this->_normalize($temp);
3049. 3049     }
3050. 3050 
3051. 3051     /**
3052. 3052      * Logical Left Rotate
3053. 3053      *
3054. 3054      * Instead of the top x bits being dropped they're appended to the shifted bit string.
3055. 3055      *
3056. 3056      * @param int $shift
3057. 3057      * @return Math_BigInteger
3058. 3058      * @access public
3059. 3059      */
3060. 3060     function bitwise_leftRotate($shift)
3061. 3061     {
3062. 3062         $bits = $this->toBytes();
3063. 3063 
3064. 3064         if ($this->precision > 0) {
3065. 3065             $precision = $this->precision;
3066. 3066             if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
3067. 3067                 $mask = $this->bitmask->subtract(new Math_BigInteger(1));
3068. 3068                 $mask = $mask->toBytes();
3069. 3069             } else {
3070. 3070                 $mask = $this->bitmask->toBytes();
3071. 3071             }
3072. 3072         } else {
3073. 3073             $temp = ord($bits[0]);
3074. 3074             for ($i = 0; $temp >> $i; ++$i) {
3075. 3075             }
3076. 3076             $precision = 8 * strlen($bits) - 8 + $i;
3077. 3077             $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
3078. 3078         }
3079. 3079 
3080. 3080         if ($shift < 0) {
3081. 3081             $shift+= $precision;
3082. 3082         }
3083. 3083         $shift%= $precision;
3084. 3084 
3085. 3085         if (!$shift) {
3086. 3086             return $this->copy();
3087. 3087         }
3088. 3088 
3089. 3089         $left = $this->bitwise_leftShift($shift);
3090. 3090         $left = $left->bitwise_and(new Math_BigInteger($mask, 256));
3091. 3091         $right = $this->bitwise_rightShift($precision - $shift);
3092. 3092         $result = MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
3093. 3093         return $this->_normalize($result);
3094. 3094     }
3095. 3095 
3096. 3096     /**
3097. 3097      * Logical Right Rotate
3098. 3098      *
3099. 3099      * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
3100. 3100      *
3101. 3101      * @param int $shift
3102. 3102      * @return Math_BigInteger
3103. 3103      * @access public
3104. 3104      */
3105. 3105     function bitwise_rightRotate($shift)
3106. 3106     {
3107. 3107         return $this->bitwise_leftRotate(-$shift);
3108. 3108     }
3109. 3109 
3110. 3110     /**
3111. 3111      * Set random number generator function
3112. 3112      *
3113. 3113      * This function is deprecated.
3114. 3114      *
3115. 3115      * @param string $generator
3116. 3116      * @access public
3117. 3117      */
3118. 3118     function setRandomGenerator($generator)
3119. 3119     {
3120. 3120     }
3121. 3121 
3122. 3122     /**
3123. 3123      * Generates a random BigInteger
3124. 3124      *
3125. 3125      * Byte length is equal to $length. Uses crypt_random if it's loaded and mt_rand if it's not.
3126. 3126      *
3127. 3127      * @param int $length
3128. 3128      * @return Math_BigInteger
3129. 3129      * @access private
3130. 3130      */
3131. 3131     function _random_number_helper($size)
3132. 3132     {
3133. 3133         if (function_exists('crypt_random_string')) {
3134. 3134             $random = crypt_random_string($size);
3135. 3135         } else {
3136. 3136             $random = '';
3137. 3137 
3138. 3138             if ($size & 1) {
3139. 3139                 $random.= chr(mt_rand(0, 255));
3140. 3140             }
3141. 3141 
3142. 3142             $blocks = $size >> 1;
3143. 3143             for ($i = 0; $i < $blocks; ++$i) {
3144. 3144                 // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
3145. 3145                 $random.= pack('n', mt_rand(0, 0xFFFF));
3146. 3146             }
3147. 3147         }
3148. 3148 
3149. 3149         return new Math_BigInteger($random, 256);
3150. 3150     }
3151. 3151 
3152. 3152     /**
3153. 3153      * Generate a random number
3154. 3154      *
3155. 3155      * Returns a random number between $min and $max where $min and $max
3156. 3156      * can be defined using one of the two methods:
3157. 3157      *
3158. 3158      * $min->random($max)
3159. 3159      * $max->random($min)
3160. 3160      *
3161. 3161      * @param Math_BigInteger $arg1
3162. 3162      * @param Math_BigInteger $arg2
3163. 3163      * @return Math_BigInteger
3164. 3164      * @access public
3165. 3165      * @internal The API for creating random numbers used to be $a->random($min, $max), where $a was a Math_BigInteger object.
3166. 3166      *           That method is still supported for BC purposes.
3167. 3167      */
3168. 3168     function random($arg1, $arg2 = false)
3169. 3169     {
3170. 3170         if ($arg1 === false) {
3171. 3171             return false;
3172. 3172         }
3173. 3173 
3174. 3174         if ($arg2 === false) {
3175. 3175             $max = $arg1;
3176. 3176             $min = $this;
3177. 3177         } else {
3178. 3178             $min = $arg1;
3179. 3179             $max = $arg2;
3180. 3180         }
3181. 3181 
3182. 3182         $compare = $max->compare($min);
3183. 3183 
3184. 3184         if (!$compare) {
3185. 3185             return $this->_normalize($min);
3186. 3186         } elseif ($compare < 0) {
3187. 3187             // if $min is bigger then $max, swap $min and $max
3188. 3188             $temp = $max;
3189. 3189             $max = $min;
3190. 3190             $min = $temp;
3191. 3191         }
3192. 3192 
3193. 3193         static $one;
3194. 3194         if (!isset($one)) {
3195. 3195             $one = new Math_BigInteger(1);
3196. 3196         }
3197. 3197 
3198. 3198         $max = $max->subtract($min->subtract($one));
3199. 3199         $size = strlen(ltrim($max->toBytes(), chr(0)));
3200. 3200 
3201. 3201         /*
3202. 3202             doing $random % $max doesn't work because some numbers will be more likely to occur than others.
3203. 3203             eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
3204. 3204             would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
3205. 3205             not all numbers would be equally likely. some would be more likely than others.
3206. 3206 
3207. 3207             creating a whole new random number until you find one that is within the range doesn't work
3208. 3208             because, for sufficiently small ranges, the likelihood that you'd get a number within that range
3209. 3209             would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
3210. 3210             would be pretty high that $random would be greater than $max.
3211. 3211 
3212. 3212             phpseclib works around this using the technique described here:
3213. 3213 
3214. 3214             http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
3215. 3215         */
3216. 3216         $random_max = new Math_BigInteger(chr(1) . str_repeat("\0", $size), 256);
3217. 3217         $random = $this->_random_number_helper($size);
3218. 3218 
3219. 3219         list($max_multiple) = $random_max->divide($max);
3220. 3220         $max_multiple = $max_multiple->multiply($max);
3221. 3221 
3222. 3222         while ($random->compare($max_multiple) >= 0) {
3223. 3223             $random = $random->subtract($max_multiple);
3224. 3224             $random_max = $random_max->subtract($max_multiple);
3225. 3225             $random = $random->bitwise_leftShift(8);
3226. 3226             $random = $random->add($this->_random_number_helper(1));
3227. 3227             $random_max = $random_max->bitwise_leftShift(8);
3228. 3228             list($max_multiple) = $random_max->divide($max);
3229. 3229             $max_multiple = $max_multiple->multiply($max);
3230. 3230         }
3231. 3231         list(, $random) = $random->divide($max);
3232. 3232 
3233. 3233         return $this->_normalize($random->add($min));
3234. 3234     }
3235. 3235 
3236. 3236     /**
3237. 3237      * Generate a random prime number.
3238. 3238      *
3239. 3239      * If there's not a prime within the given range, false will be returned.
3240. 3240      * If more than $timeout seconds have elapsed, give up and return false.
3241. 3241      *
3242. 3242      * @param Math_BigInteger $arg1
3243. 3243      * @param Math_BigInteger $arg2
3244. 3244      * @param int $timeout
3245. 3245      * @return Math_BigInteger|false
3246. 3246      * @access public
3247. 3247      * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}.
3248. 3248      */
3249. 3249     function randomPrime($arg1, $arg2 = false, $timeout = false)
3250. 3250     {
3251. 3251         if ($arg1 === false) {
3252. 3252             return false;
3253. 3253         }
3254. 3254 
3255. 3255         if ($arg2 === false) {
3256. 3256             $max = $arg1;
3257. 3257             $min = $this;
3258. 3258         } else {
3259. 3259             $min = $arg1;
3260. 3260             $max = $arg2;
3261. 3261         }
3262. 3262 
3263. 3263         $compare = $max->compare($min);
3264. 3264 
3265. 3265         if (!$compare) {
3266. 3266             return $min->isPrime() ? $min : false;
3267. 3267         } elseif ($compare < 0) {
3268. 3268             // if $min is bigger then $max, swap $min and $max
3269. 3269             $temp = $max;
3270. 3270             $max = $min;
3271. 3271             $min = $temp;
3272. 3272         }
3273. 3273 
3274. 3274         static $one, $two;
3275. 3275         if (!isset($one)) {
3276. 3276             $one = new Math_BigInteger(1);
3277. 3277             $two = new Math_BigInteger(2);
3278. 3278         }
3279. 3279 
3280. 3280         $start = time();
3281. 3281 
3282. 3282         $x = $this->random($min, $max);
3283. 3283 
3284. 3284         // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
3285. 3285         if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP && extension_loaded('gmp') && version_compare(PHP_VERSION, '5.2.0', '>=')) {
3286. 3286             $p = new Math_BigInteger();
3287. 3287             $p->value = gmp_nextprime($x->value);
3288. 3288 
3289. 3289             if ($p->compare($max) <= 0) {
3290. 3290                 return $p;
3291. 3291             }
3292. 3292 
3293. 3293             if (!$min->equals($x)) {
3294. 3294                 $x = $x->subtract($one);
3295. 3295             }
3296. 3296 
3297. 3297             return $x->randomPrime($min, $x);
3298. 3298         }
3299. 3299 
3300. 3300         if ($x->equals($two)) {
3301. 3301             return $x;
3302. 3302         }
3303. 3303 
3304. 3304         $x->_make_odd();
3305. 3305         if ($x->compare($max) > 0) {
3306. 3306             // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
3307. 3307             if ($min->equals($max)) {
3308. 3308                 return false;
3309. 3309             }
3310. 3310             $x = $min->copy();
3311. 3311             $x->_make_odd();
3312. 3312         }
3313. 3313 
3314. 3314         $initial_x = $x->copy();
3315. 3315 
3316. 3316         while (true) {
3317. 3317             if ($timeout !== false && time() - $start > $timeout) {
3318. 3318                 return false;
3319. 3319             }
3320. 3320 
3321. 3321             if ($x->isPrime()) {
3322. 3322                 return $x;
3323. 3323             }
3324. 3324 
3325. 3325             $x = $x->add($two);
3326. 3326 
3327. 3327             if ($x->compare($max) > 0) {
3328. 3328                 $x = $min->copy();
3329. 3329                 if ($x->equals($two)) {
3330. 3330                     return $x;
3331. 3331                 }
3332. 3332                 $x->_make_odd();
3333. 3333             }
3334. 3334 
3335. 3335             if ($x->equals($initial_x)) {
3336. 3336                 return false;
3337. 3337             }
3338. 3338         }
3339. 3339     }
3340. 3340 
3341. 3341     /**
3342. 3342      * Make the current number odd
3343. 3343      *
3344. 3344      * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
3345. 3345      *
3346. 3346      * @see self::randomPrime()
3347. 3347      * @access private
3348. 3348      */
3349. 3349     function _make_odd()
3350. 3350     {
3351. 3351         switch (MATH_BIGINTEGER_MODE) {
3352. 3352             case MATH_BIGINTEGER_MODE_GMP:
3353. 3353                 gmp_setbit($this->value, 0);
3354. 3354                 break;
3355. 3355             case MATH_BIGINTEGER_MODE_BCMATH:
3356. 3356                 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3357. 3357                     $this->value = bcadd($this->value, '1');
3358. 3358                 }
3359. 3359                 break;
3360. 3360             default:
3361. 3361                 $this->value[0] |= 1;
3362. 3362         }
3363. 3363     }
3364. 3364 
3365. 3365     /**
3366. 3366      * Checks a numer to see if it's prime
3367. 3367      *
3368. 3368      * Assuming the $t parameter is not set, this function has an error rate of 2**-80.  The main motivation for the
3369. 3369      * $t parameter is distributability.  Math_BigInteger::randomPrime() can be distributed across multiple pageloads
3370. 3370      * on a website instead of just one.
3371. 3371      *
3372. 3372      * @param Math_BigInteger $t
3373. 3373      * @return bool
3374. 3374      * @access public
3375. 3375      * @internal Uses the
3376. 3376      *     {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}.  See
3377. 3377      *     {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}.
3378. 3378      */
3379. 3379     function isPrime($t = false)
3380. 3380     {
3381. 3381         $length = strlen($this->toBytes());
3382. 3382 
3383. 3383         if (!$t) {
3384. 3384             // see HAC 4.49 "Note (controlling the error probability)"
3385. 3385             // @codingStandardsIgnoreStart
3386. 3386                  if ($length >= 163) { $t =  2; } // floor(1300 / 8)
3387. 3387             else if ($length >= 106) { $t =  3; } // floor( 850 / 8)
3388. 3388             else if ($length >= 81 ) { $t =  4; } // floor( 650 / 8)
3389. 3389             else if ($length >= 68 ) { $t =  5; } // floor( 550 / 8)
3390. 3390             else if ($length >= 56 ) { $t =  6; } // floor( 450 / 8)
3391. 3391             else if ($length >= 50 ) { $t =  7; } // floor( 400 / 8)
3392. 3392             else if ($length >= 43 ) { $t =  8; } // floor( 350 / 8)
3393. 3393             else if ($length >= 37 ) { $t =  9; } // floor( 300 / 8)
3394. 3394             else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
3395. 3395             else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
3396. 3396             else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
3397. 3397             else                     { $t = 27; }
3398. 3398             // @codingStandardsIgnoreEnd
3399. 3399         }
3400. 3400 
3401. 3401         // ie. gmp_testbit($this, 0)
3402. 3402         // ie. isEven() or !isOdd()
3403. 3403         switch (MATH_BIGINTEGER_MODE) {
3404. 3404             case MATH_BIGINTEGER_MODE_GMP:
3405. 3405                 return gmp_prob_prime($this->value, $t) != 0;
3406. 3406             case MATH_BIGINTEGER_MODE_BCMATH:
3407. 3407                 if ($this->value === '2') {
3408. 3408                     return true;
3409. 3409                 }
3410. 3410                 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3411. 3411                     return false;
3412. 3412                 }
3413. 3413                 break;
3414. 3414             default:
3415. 3415                 if ($this->value == array(2)) {
3416. 3416                     return true;
3417. 3417                 }
3418. 3418                 if (~$this->value[0] & 1) {
3419. 3419                     return false;
3420. 3420                 }
3421. 3421         }
3422. 3422 
3423. 3423         static $primes, $zero, $one, $two;
3424. 3424 
3425. 3425         if (!isset($primes)) {
3426. 3426             $primes = array(
3427. 3427                 3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,   41,   43,   47,   53,   59,
3428. 3428                 61,   67,   71,   73,   79,   83,   89,   97,   101,  103,  107,  109,  113,  127,  131,  137,
3429. 3429                 139,  149,  151,  157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,  227,
3430. 3430                 229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  283,  293,  307,  311,  313,
3431. 3431                 317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,  397,  401,  409,  419,
3432. 3432                 421,  431,  433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,  509,
3433. 3433                 521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,  599,  601,  607,  613,  617,
3434. 3434                 619,  631,  641,  643,  647,  653,  659,  661,  673,  677,  683,  691,  701,  709,  719,  727,
3435. 3435                 733,  739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,  829,
3436. 3436                 839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,  919,  929,  937,  941,  947,
3437. 3437                 953,  967,  971,  977,  983,  991,  997
3438. 3438             );
3439. 3439 
3440. 3440             if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
3441. 3441                 for ($i = 0; $i < count($primes); ++$i) {
3442. 3442                     $primes[$i] = new Math_BigInteger($primes[$i]);
3443. 3443                 }
3444. 3444             }
3445. 3445 
3446. 3446             $zero = new Math_BigInteger();
3447. 3447             $one = new Math_BigInteger(1);
3448. 3448             $two = new Math_BigInteger(2);
3449. 3449         }
3450. 3450 
3451. 3451         if ($this->equals($one)) {
3452. 3452             return false;
3453. 3453         }
3454. 3454 
3455. 3455         // see HAC 4.4.1 "Random search for probable primes"
3456. 3456         if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
3457. 3457             foreach ($primes as $prime) {
3458. 3458                 list(, $r) = $this->divide($prime);
3459. 3459                 if ($r->equals($zero)) {
3460. 3460                     return $this->equals($prime);
3461. 3461                 }
3462. 3462             }
3463. 3463         } else {
3464. 3464             $value = $this->value;
3465. 3465             foreach ($primes as $prime) {
3466. 3466                 list(, $r) = $this->_divide_digit($value, $prime);
3467. 3467                 if (!$r) {
3468. 3468                     return count($value) == 1 && $value[0] == $prime;
3469. 3469                 }
3470. 3470             }
3471. 3471         }
3472. 3472 
3473. 3473         $n   = $this->copy();
3474. 3474         $n_1 = $n->subtract($one);
3475. 3475         $n_2 = $n->subtract($two);
3476. 3476 
3477. 3477         $r = $n_1->copy();
3478. 3478         $r_value = $r->value;
3479. 3479         // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
3480. 3480         if (MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH) {
3481. 3481             $s = 0;
3482. 3482             // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
3483. 3483             while ($r->value[strlen($r->value) - 1] % 2 == 0) {
3484. 3484                 $r->value = bcdiv($r->value, '2', 0);
3485. 3485                 ++$s;
3486. 3486             }
3487. 3487         } else {
3488. 3488             for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
3489. 3489                 $temp = ~$r_value[$i] & 0xFFFFFF;
3490. 3490                 for ($j = 1; ($temp >> $j) & 1; ++$j) {
3491. 3491                 }
3492. 3492                 if ($j != 25) {
3493. 3493                     break;
3494. 3494                 }
3495. 3495             }
3496. 3496             $s = 26 * $i + $j;
3497. 3497             $r->_rshift($s);
3498. 3498         }
3499. 3499 
3500. 3500         for ($i = 0; $i < $t; ++$i) {
3501. 3501             $a = $this->random($two, $n_2);
3502. 3502             $y = $a->modPow($r, $n);
3503. 3503 
3504. 3504             if (!$y->equals($one) && !$y->equals($n_1)) {
3505. 3505                 for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
3506. 3506                     $y = $y->modPow($two, $n);
3507. 3507                     if ($y->equals($one)) {
3508. 3508                         return false;
3509. 3509                     }
3510. 3510                 }
3511. 3511 
3512. 3512                 if (!$y->equals($n_1)) {
3513. 3513                     return false;
3514. 3514                 }
3515. 3515             }
3516. 3516         }
3517. 3517         return true;
3518. 3518     }
3519. 3519 
3520. 3520     /**
3521. 3521      * Logical Left Shift
3522. 3522      *
3523. 3523      * Shifts BigInteger's by $shift bits.
3524. 3524      *
3525. 3525      * @param int $shift
3526. 3526      * @access private
3527. 3527      */
3528. 3528     function _lshift($shift)
3529. 3529     {
3530. 3530         if ($shift == 0) {
3531. 3531             return;
3532. 3532         }
3533. 3533 
3534. 3534         $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
3535. 3535         $shift %= MATH_BIGINTEGER_BASE;
3536. 3536         $shift = 1 << $shift;
3537. 3537 
3538. 3538         $carry = 0;
3539. 3539 
3540. 3540         for ($i = 0; $i < count($this->value); ++$i) {
3541. 3541             $temp = $this->value[$i] * $shift + $carry;
3542. 3542             $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
3543. 3543             $this->value[$i] = (int) ($temp - $carry * MATH_BIGINTEGER_BASE_FULL);
3544. 3544         }
3545. 3545 
3546. 3546         if ($carry) {
3547. 3547             $this->value[count($this->value)] = $carry;
3548. 3548         }
3549. 3549 
3550. 3550         while ($num_digits--) {
3551. 3551             array_unshift($this->value, 0);
3552. 3552         }
3553. 3553     }
3554. 3554 
3555. 3555     /**
3556. 3556      * Logical Right Shift
3557. 3557      *
3558. 3558      * Shifts BigInteger's by $shift bits.
3559. 3559      *
3560. 3560      * @param int $shift
3561. 3561      * @access private
3562. 3562      */
3563. 3563     function _rshift($shift)
3564. 3564     {
3565. 3565         if ($shift == 0) {
3566. 3566             return;
3567. 3567         }
3568. 3568 
3569. 3569         $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
3570. 3570         $shift %= MATH_BIGINTEGER_BASE;
3571. 3571         $carry_shift = MATH_BIGINTEGER_BASE - $shift;
3572. 3572         $carry_mask = (1 << $shift) - 1;
3573. 3573 
3574. 3574         if ($num_digits) {
3575. 3575             $this->value = array_slice($this->value, $num_digits);
3576. 3576         }
3577. 3577 
3578. 3578         $carry = 0;
3579. 3579 
3580. 3580         for ($i = count($this->value) - 1; $i >= 0; --$i) {
3581. 3581             $temp = $this->value[$i] >> $shift | $carry;
3582. 3582             $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
3583. 3583             $this->value[$i] = $temp;
3584. 3584         }
3585. 3585 
3586. 3586         $this->value = $this->_trim($this->value);
3587. 3587     }
3588. 3588 
3589. 3589     /**
3590. 3590      * Normalize
3591. 3591      *
3592. 3592      * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
3593. 3593      *
3594. 3594      * @param Math_BigInteger
3595. 3595      * @return Math_BigInteger
3596. 3596      * @see self::_trim()
3597. 3597      * @access private
3598. 3598      */
3599. 3599     function _normalize($result)
3600. 3600     {
3601. 3601         $result->precision = $this->precision;
3602. 3602         $result->bitmask = $this->bitmask;
3603. 3603 
3604. 3604         switch (MATH_BIGINTEGER_MODE) {
3605. 3605             case MATH_BIGINTEGER_MODE_GMP:
3606. 3606                 if ($this->bitmask !== false) {
3607. 3607                     $result->value = gmp_and($result->value, $result->bitmask->value);
3608. 3608                 }
3609. 3609 
3610. 3610                 return $result;
3611. 3611             case MATH_BIGINTEGER_MODE_BCMATH:
3612. 3612                 if (!empty($result->bitmask->value)) {
3613. 3613                     $result->value = bcmod($result->value, $result->bitmask->value);
3614. 3614                 }
3615. 3615 
3616. 3616                 return $result;
3617. 3617         }
3618. 3618 
3619. 3619         $value = &$result->value;
3620. 3620 
3621. 3621         if (!count($value)) {
3622. 3622             return $result;
3623. 3623         }
3624. 3624 
3625. 3625         $value = $this->_trim($value);
3626. 3626 
3627. 3627         if (!empty($result->bitmask->value)) {
3628. 3628             $length = min(count($value), count($this->bitmask->value));
3629. 3629             $value = array_slice($value, 0, $length);
3630. 3630 
3631. 3631             for ($i = 0; $i < $length; ++$i) {
3632. 3632                 $value[$i] = $value[$i] & $this->bitmask->value[$i];
3633. 3633             }
3634. 3634         }
3635. 3635 
3636. 3636         return $result;
3637. 3637     }
3638. 3638 
3639. 3639     /**
3640. 3640      * Trim
3641. 3641      *
3642. 3642      * Removes leading zeros
3643. 3643      *
3644. 3644      * @param array $value
3645. 3645      * @return Math_BigInteger
3646. 3646      * @access private
3647. 3647      */
3648. 3648     function _trim($value)
3649. 3649     {
3650. 3650         for ($i = count($value) - 1; $i >= 0; --$i) {
3651. 3651             if ($value[$i]) {
3652. 3652                 break;
3653. 3653             }
3654. 3654             unset($value[$i]);
3655. 3655         }
3656. 3656 
3657. 3657         return $value;
3658. 3658     }
3659. 3659 
3660. 3660     /**
3661. 3661      * Array Repeat
3662. 3662      *
3663. 3663      * @param $input Array
3664. 3664      * @param $multiplier mixed
3665. 3665      * @return array
3666. 3666      * @access private
3667. 3667      */
3668. 3668     function _array_repeat($input, $multiplier)
3669. 3669     {
3670. 3670         return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
3671. 3671     }
3672. 3672 
3673. 3673     /**
3674. 3674      * Logical Left Shift
3675. 3675      *
3676. 3676      * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
3677. 3677      *
3678. 3678      * @param $x String
3679. 3679      * @param $shift Integer
3680. 3680      * @return string
3681. 3681      * @access private
3682. 3682      */
3683. 3683     function _base256_lshift(&$x, $shift)
3684. 3684     {
3685. 3685         if ($shift == 0) {
3686. 3686             return;
3687. 3687         }
3688. 3688 
3689. 3689         $num_bytes = $shift >> 3; // eg. floor($shift/8)
3690. 3690         $shift &= 7; // eg. $shift % 8
3691. 3691 
3692. 3692         $carry = 0;
3693. 3693         for ($i = strlen($x) - 1; $i >= 0; --$i) {
3694. 3694             $temp = ord($x[$i]) << $shift | $carry;
3695. 3695             $x[$i] = chr($temp);
3696. 3696             $carry = $temp >> 8;
3697. 3697         }
3698. 3698         $carry = ($carry != 0) ? chr($carry) : '';
3699. 3699         $x = $carry . $x . str_repeat(chr(0), $num_bytes);
3700. 3700     }
3701. 3701 
3702. 3702     /**
3703. 3703      * Logical Right Shift
3704. 3704      *
3705. 3705      * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
3706. 3706      *
3707. 3707      * @param $x String
3708. 3708      * @param $shift Integer
3709. 3709      * @return string
3710. 3710      * @access private
3711. 3711      */
3712. 3712     function _base256_rshift(&$x, $shift)
3713. 3713     {
3714. 3714         if ($shift == 0) {
3715. 3715             $x = ltrim($x, chr(0));
3716. 3716             return '';
3717. 3717         }
3718. 3718 
3719. 3719         $num_bytes = $shift >> 3; // eg. floor($shift/8)
3720. 3720         $shift &= 7; // eg. $shift % 8
3721. 3721 
3722. 3722         $remainder = '';
3723. 3723         if ($num_bytes) {
3724. 3724             $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
3725. 3725             $remainder = substr($x, $start);
3726. 3726             $x = substr($x, 0, -$num_bytes);
3727. 3727         }
3728. 3728 
3729. 3729         $carry = 0;
3730. 3730         $carry_shift = 8 - $shift;
3731. 3731         for ($i = 0; $i < strlen($x); ++$i) {
3732. 3732             $temp = (ord($x[$i]) >> $shift) | $carry;
3733. 3733             $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
3734. 3734             $x[$i] = chr($temp);
3735. 3735         }
3736. 3736         $x = ltrim($x, chr(0));
3737. 3737 
3738. 3738         $remainder = chr($carry >> $carry_shift) . $remainder;
3739. 3739 
3740. 3740         return ltrim($remainder, chr(0));
3741. 3741     }
3742. 3742 
3743. 3743     // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
3744. 3744     // at 32-bits, while java's longs are 64-bits.
3745. 3745 
3746. 3746     /**
3747. 3747      * Converts 32-bit integers to bytes.
3748. 3748      *
3749. 3749      * @param int $x
3750. 3750      * @return string
3751. 3751      * @access private
3752. 3752      */
3753. 3753     function _int2bytes($x)
3754. 3754     {
3755. 3755         return ltrim(pack('N', $x), chr(0));
3756. 3756     }
3757. 3757 
3758. 3758     /**
3759. 3759      * Converts bytes to 32-bit integers
3760. 3760      *
3761. 3761      * @param string $x
3762. 3762      * @return int
3763. 3763      * @access private
3764. 3764      */
3765. 3765     function _bytes2int($x)
3766. 3766     {
3767. 3767         $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
3768. 3768         return $temp['int'];
3769. 3769     }
3770. 3770 
3771. 3771     /**
3772. 3772      * DER-encode an integer
3773. 3773      *
3774. 3774      * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL
3775. 3775      *
3776. 3776      * @see self::modPow()
3777. 3777      * @access private
3778. 3778      * @param int $length
3779. 3779      * @return string
3780. 3780      */
3781. 3781     function _encodeASN1Length($length)
3782. 3782     {
3783. 3783         if ($length <= 0x7F) {
3784. 3784             return chr($length);
3785. 3785         }
3786. 3786 
3787. 3787         $temp = ltrim(pack('N', $length), chr(0));
3788. 3788         return pack('Ca*', 0x80 | strlen($temp), $temp);
3789. 3789     }
3790. 3790 
3791. 3791     /**
3792. 3792      * Single digit division
3793. 3793      *
3794. 3794      * Even if int64 is being used the division operator will return a float64 value
3795. 3795      * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't
3796. 3796      * have the precision of int64 this is a problem so, when int64 is being used,
3797. 3797      * we'll guarantee that the dividend is divisible by first subtracting the remainder.
3798. 3798      *
3799. 3799      * @access private
3800. 3800      * @param int $x
3801. 3801      * @param int $y
3802. 3802      * @return int
3803. 3803      */
3804. 3804     function _safe_divide($x, $y)
3805. 3805     {
3806. 3806         if (MATH_BIGINTEGER_BASE === 26) {
3807. 3807             return (int) ($x / $y);
3808. 3808         }
3809. 3809 
3810. 3810         // MATH_BIGINTEGER_BASE === 31
3811. 3811         return ($x - ($x % $y)) / $y;
3812. 3812     }
3813. 3813 }